搜索旋转排序数组

LeetCode 33：二分时判断哪一半有序，再决定收缩区间。

#resource / algorithm #type / howto #status / evergreen #source / leetcode #algo / binary-search #ds / array

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

搜索旋转排序数组

题目

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

思路

数组由一个有序数组旋转得到，任意时刻 [l, mid] 或 [mid, r] 至少有一半是有序的。

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

代码（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;
};