搜索旋转排序数组 - Stellar Observer Protocol

843 字

4 分钟

搜索旋转排序数组

2025-08-08

Algorithms

数组

/

二分查找

题目描述#

整数数组 nums 按升序排列，数组中的值 互不相同 。

在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了旋转，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。

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

你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

解题思路#

二分查找框架：
- 初始化左右指针 left = 0, right = nums.length - 1
- 循环条件 while (left <= right)
判断区间有序性：
- 计算中点 mid = (left + right) >> 1
- 若 nums[left] <= nums[mid] → 左区间有序
- 否则 → 右区间有序
目标值检测：
- 左区间有序时：
  - 若 target ∈ [nums[left], nums[mid]) → 右移右指针 right = mid - 1
  - 否则 → 左移左指针 left = mid + 1
- 右区间有序时：
  - 若 target ∈ (nums[mid], nums[right]] → 左移左指针 left = mid + 1
  - 否则 → 右移右指针 right = mid - 1
终止条件：
- nums[mid] === target 时立即返回索引
- 循环结束未找到则返回 -1

关键洞察#

局部有序性：
- 旋转数组 必有一侧区间保持有序
- 通过 nums[left] <= nums[mid] 快速判定有序区间
区间选择逻辑：
- 目标值在有序区间内 → 继续搜索该区间
- 目标值在无序区间 → 转向另一侧区间搜索
- 本质是 利用有序性缩小搜索范围
边界精确控制：
- 比较时包含等号（如 <=, >=）防止遗漏边界值
- 区间端点值必须参与判断（旋转点可能在任意位置）
对数复杂度保证：
- 每次迭代排除一半区间 → O(log n) 时间复杂度
- 空间复杂度 O(1)（仅需指针变量）

复杂度分析#

类型	复杂度	说明
时间复杂度	O(log n)	二分查找每次排除一半区间
空间复杂度	O(1)	仅使用常量级额外空间

代码实现#

1
var search = function (nums, target) {
2
    let left = 0, right = nums.length - 1;
3
    while (left <= right) {
4
        const mid = left + Math.floor((right - left) / 2);
5
        // 找到目标值直接返回
6
        if (nums[mid] === target) return mid;
7
        // 左半部分有序（包括旋转点不在左半部分的情况）
8
        if (nums[left] <= nums[mid]) {
9
            // 目标值在有序的左半部分区间内
10
            if (nums[left] <= target && target < nums[mid]) {
11
                right = mid - 1;
12
            } else {
13
                left = mid + 1;
14
            }
15
        }
16
        // 右半部分有序
17
        else {
18
            // 目标值在有序的右半部分区间内
19
            if (nums[mid] < target && target <= nums[right]) {
20
                left = mid + 1;
21
            } else {
22
                right = mid - 1;
23
            }
24
        }
25
    }
26
    return -1;  // 未找到目标值
27
};