Search in Rotated Sorted Array

在旋转有序数组中查找目标值。

在旋转有序数组中用 O(log n) 查找目标值。关键在于每次二分后，总有一半区间仍然保持有序。

ArrayBinary Search

题目定位

每一步总有一半仍然保持有序，因此关键是判断哪一半有序，以及目标值是否落在那一半里。

关键观察

不是随便比较 target 和某个数，而是利用“哪一半有序”的结构来安全淘汰半边区间。

目标复杂度

O(log n) / O(1)

这题的解法思路怎么拆

先正常二分，但第一步不是直接比较大小，而是先判断哪一半有序。

如果左半边有序，就判断 target 是否落在这个有序区间内。

否则右半边一定有序，再判断 target 是否属于右半边。

淘汰不可能包含答案的那一半，继续二分。

拿一个例子顺一遍

例如 nums = [4,5,6,7,0,1,2], target = 0。

mid 指到 7，此时左半边 [4,5,6,7] 有序。

target 0 不在左半边，所以收缩到右半边。

再做一次同样判断，就能定位到下标 4。

参考实现

Python

def search(nums: list[int], target: int) -> int:
    left, right = 0, len(nums) - 1

    while left <= right:
        mid = (left + right) // 2
        if nums[mid] == target:
            return mid

        if nums[left] <= nums[mid]:
            if nums[left] <= target < nums[mid]:
                right = mid - 1
            else:
                left = mid + 1
        else:
            if nums[mid] < target <= nums[right]:
                left = mid + 1
            else:
                right = mid - 1

    return -1

TypeScript 版本

TypeScript

function search(nums: number[], target: number): number {
  let left = 0;
  let right = nums.length - 1;

  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    if (nums[mid] === target) {
      return mid;
    }

    if (nums[left] <= nums[mid]) {
      if (nums[left] <= target && target < nums[mid]) {
        right = mid - 1;
      } else {
        left = mid + 1;
      }
    } else {
      if (nums[mid] < target && target <= nums[right]) {
        left = mid + 1;
      } else {
        right = mid - 1;
      }
    }
  }

  return -1;
}