跳到主要内容

搜索旋转排序数组

问题​

整数数组 nums 按升序排列，数组中的值互不相同。在传递给函数之前，nums 在某个未知下标 k 处进行了旋转（例如 [0,1,2,4,5,6,7] 旋转后变为 [4,5,6,7,0,1,2]）。

给你旋转后的数组 nums 和一个整数 target，如果 target 存在则返回其下标，否则返回 -1。

要求：时间复杂度 O(log⁡n)O(\log n)。

示例：

输入：nums = [4,5,6,7,0,1,2], target = 0
输出：4

输入：nums = [4,5,6,7,0,1,2], target = 3
输出：-1

来源：LeetCode 33. 搜索旋转排序数组

答案​

方法一：二分查找（推荐）​

核心思路：旋转后的数组被分成两段有序部分。通过 nums[mid] 和 nums[left] 的比较判断 mid 在哪段有序部分中，然后决定搜索方向。

search.ts
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;

    // 判断 mid 在左半段还是右半段
    if (nums[left] <= nums[mid]) {
      // 左半段有序 [left ... mid]
      if (target >= nums[left] && target < nums[mid]) {
        right = mid - 1; // target 在左半段
      } else {
        left = mid + 1;  // target 在右半段
      }
    } else {
      // 右半段有序 [mid ... right]
      if (target > nums[mid] && target <= nums[right]) {
        left = mid + 1;  // target 在右半段
      } else {
        right = mid - 1; // target 在左半段
      }
    }
  }

  return -1;
}

图解（nums = [4,5,6,7,0,1,2], target = 0）：

Step 1: left=0, right=6, mid=3
  nums[3]=7, nums[0]=4 ≤ 7 → 左半段有序 [4,5,6,7]
  target=0 不在 [4,7) 中 → left = 4

Step 2: left=4, right=6, mid=5
  nums[5]=1, nums[4]=0 ≤ 1 → 左半段有序 [0,1]
  target=0 在 [0,1) 中 → right = 4

Step 3: left=4, right=4, mid=4
  nums[4]=0 = target → 返回 4
复杂度分析
  • 时间复杂度：O(log⁡n)O(\log n) — 标准二分
  • 空间复杂度：O(1)O(1)
关键判断条件

nums[left] <= nums[mid]（注意是 <= 不是 <）。 当 left === mid 时（只有两个元素），也应该认为左半段有序。

方法二：先找旋转点，再二分​

searchTwoPass.ts
function search(nums: number[], target: number): number {
  const n = nums.length;

  // 1. 找到旋转点（最小值位置）
  let lo = 0, hi = n - 1;
  while (lo < hi) {
    const mid = Math.floor((lo + hi) / 2);
    if (nums[mid] > nums[hi]) {
      lo = mid + 1;
    } else {
      hi = mid;
    }
  }
  const pivot = lo; // 最小值的索引

  // 2. 确定 target 在哪一段，然后标准二分
  if (target >= nums[pivot] && target <= nums[n - 1]) {
    lo = pivot;
    hi = n - 1;
  } else {
    lo = 0;
    hi = pivot - 1;
  }

  // 3. 标准二分查找
  while (lo <= hi) {
    const mid = Math.floor((lo + hi) / 2);
    if (nums[mid] === target) return mid;
    if (nums[mid] < target) lo = mid + 1;
    else hi = mid - 1;
  }

  return -1;
}

常见面试追问​

Q1: 如果数组有重复元素呢？(LeetCode 81)​

答案：当 nums[left] === nums[mid] 时，无法确定哪一段有序，需要 left++ 跳过：

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

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

    // 无法判断时，缩小范围
    if (nums[left] === nums[mid]) {
      left++;
      continue;
    }

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

  return false;
}

最坏时间复杂度退化为 O(n)O(n)。

Q2: 如何找旋转排序数组中的最小值？(LeetCode 153)​

答案：

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

  while (left < right) {
    const mid = Math.floor((left + right) / 2);
    if (nums[mid] > nums[right]) {
      left = mid + 1; // 最小值在右半段
    } else {
      right = mid; // 最小值在左半段（包括 mid）
    }
  }

  return nums[left];
}

Q3: 二分查找的边界条件如何确定？​

答案：

写法while 条件左边界更新右边界更新适用场景
闭区间left <= rightleft = mid + 1right = mid - 1精确查找
左闭右开left < rightleft = mid + 1right = mid找左边界

核心原则：保证搜索区间不断缩小，且不遗漏答案。

相关链接​