[!info] related notes 算法面试题型 MOC 二分查找

搜索旋转排序数组

题目

33. 搜索旋转排序数组 - 力扣（LeetCode）

思路

数组由严格升序、元素互异的数组旋转得到，也允许没有实际旋转。任意时刻 [l, mid] 或 [mid, r] 至少有一半有序；先检查 mid 是否命中，再用有序侧的值域排除一半。

• 若 nums[l] <= nums[mid]，说明左半有序
  • 若 target 落在 [nums[l], nums[mid])，去左边，否则去右边
• 否则右半有序
  • 若 target 落在 (nums[mid], nums[r]]，去右边，否则去左边

重复值会破坏下面的判断，例如 [1, 0, 1, 1, 1] 中首中尾相等，不能据此直接排除左侧。带重复版本需要额外消歧，最坏可退化到 O(n)；本题互异前提下为 O(log n)，空间 O(1)。

代码（JavaScript）

var search = function(nums, target) {
  let l = 0, r = nums.length - 1;
  while (l <= r) {
    const mid = Math.floor((l + r) / 2);
    if (nums[mid] === target) return mid;

    if (nums[l] <= nums[mid]) {
      // left half is sorted
      if (nums[l] <= target && target < nums[mid]) r = mid - 1;
      else l = mid + 1;
    } else {
      // right half is sorted
      if (nums[mid] < target && target <= nums[r]) l = mid + 1;
      else r = mid - 1;
    }
  }
  return -1;
};