33. 搜索旋转排序数组

[Geekhyt]

原题链接

二分查找

先来看下有序数组的二分查找。

const search = function(nums, target) {
    let start = 0
    let end = nums.length - 1
    while (start <= end) {
        const mid = start + ((end - start) >> 1)
        if (nums[mid] === target) return mid

        if (nums[mid] < target) {
            start = mid + 1
        } else {
            end = mid - 1
        }
    }
    return -1
}

1. 再来明确，因为本题是旋转数组，我们无法直接根据 nums[mid] 与 target 的关系来定位 target 是在 mid 的左边还是右边
2. 需要分段处理，先比较 nums[mid] 与 nums[start] 的大小，来定位 mid 在左边还是右边
3. 继续定位 target，判断 target 在 mid 的左边还是右边，然后分别调整边界 start 和 end

const search = function(nums, target) {
  let start = 0
  let end = nums.length - 1

  while (start <= end) {
    const mid = start + ((end - start) >> 1)
    if (nums[mid] === target) return mid

    if (nums[mid] >= nums[start]) {
      if (target >= nums[start] && target < nums[mid]) {
        end = mid - 1
      } else {
        start = mid + 1
      }
    } else {
      if (target > nums[mid] && target <= nums[end]) {
        start = mid + 1
      } else {
        end = mid - 1
      }
    }
  }
  return -1
}

• 时间复杂度：O(logn)
• 空间复杂度：O(1)