33. Search in Rotated Sorted Array

source: https://leetcode.com/problems/longest-palindromic-substring/

Question

There is an integer array nums sorted in ascending order (with distinct values).

Prior to being passed to your function, nums is possibly rotated at an unknown pivot index k (1 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (0-indexed). For example, [0,1,2,4,5,6,7] might be rotated at pivot index 3 and become [4,5,6,7,0,1,2].

Given the array nums after the possible rotation and an integer target, return the index of target if it is in nums, or -1 if it is not in nums.

You must write an algorithm with O(log n) runtime complexity.

初想法

好像涉及Binary Search的题目都看起来特别的简单，比如4题, 但是对于特定的时间复杂度，又必须要使用。

首先看一下最简单的思路：

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var search = function (nums, target) {
  return nums.findIndex((num) => num === target);
};

二分查找

这题的一个关键是要找到一个前提：

• 数组旋转后，必然有一半是升序的

基于这一半的有序数组，去做二分查找：

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var search = function (nums, target) {
  let left = 0;
  let right = nums.length - 1;
  while (left <= right) {
    const mid = ~~((left + right) / 2);
    const v = nums[mid];
    // 找到目标
    if (v === target) return mid;
    // 数组左侧是升序
    if (v >= nums[left]) {
      // 目标在数组左侧, 缩小右边界
      if (target >= nums[left] && target < v) {
        right = mid - 1;
      } 
      // 目标不在数组左侧, 缩小左边界
      else {
        left = mid + 1;
      }
    }
    // 数组右侧是升序
    else {
      // 目标在数组右侧，缩小左边界
      if (target <= nums[right] && target > v) {
        left = mid + 1;
      }
      // 目标在数组左侧，缩小右边界
      else {
        right = mid - 1;
      }
    }
  }
  // 未找到
  return -1;
};

End

对于查找有序数组中某个元素的问题，可以优先考虑二分查找。