搜索旋转排序数组 图解题解

搜索旋转排序数组在问什么

一个原本升序、无重复元素的数组，在某个位置被整体旋转过（比如 [0,1,2,4,5,6,7] 旋转成 [4,5,6,7,0,1,2]），给定 target，要求返回它的下标，不存在返回 -1，并且明确要求 O(log n)。这个复杂度要求本身就是提示：线性扫描被排除了，题目在逼你把二分查找改造到「不完全有序」的数组上。

普通二分为什么在旋转数组上失效

二分查找的根基是单调性：数组有序时，拿 nums[mid] 和 target 比一下大小，就知道目标只可能在左半或右半，方向唯一。旋转之后数组整体不再单调，中间藏着一个从最大值跌到最小值的断点，nums[mid] 比 target 大还是小不再指示方向——目标可能在任意一侧。直接套普通二分，会在错误的一半里越找越偏。

关键观察：mid 切两半，必有一半有序

救回二分的观察是：旋转数组只有一个断点，而 mid 把区间切成两半，断点只能落进其中一半——另一半必然是完整有序的。而且哪半有序当场可判：nums[l] <= nums[mid] 说明从 l 到 mid 一路没有跨过断点，左半 [l..mid] 有序；反之断点在左半，右半 [mid..r] 有序。

拿示例 [4,5,6,7,0,1,2] 找 target = 0 验证：首轮 mid 落在 7，nums[0] = 4 <= 7，左半 [4,5,6,7] 有序，0 不在 4 到 7 之间，于是放心奔右半——一步就丢掉了一半。

为什么查有序半的值域就能安全决策

有序半的价值在于它的值域是明确的闭合范围：左半有序时值域是 nums[l] 到 nums[mid]，右半有序时是 nums[mid] 到 nums[r]。于是判断变成一道二选一：target 落在这个范围里，它若存在就只能在有序半，收缩过去；不在范围里，则只可能藏在另一半（那半虽然乱，但排除法保证方向正确）。

每一轮无论走哪个分支，区间都严格减半，这就是 O(log n) 的来源。二分不怕那一半内部乱，怕的是不知道往哪走——有序半的值域恰好提供了永远可靠的路标。

复杂度与边界符号怎么写才不错

时间 O(log n)，最多 log₂n 轮；空间 O(1)，只用 l、mid、r 三个下标。边界符号是这题的雷区：判左半有序要用 nums[l] <= nums[mid]（含等号，兼容区间只剩一个元素的情形）；判值域时左半用 nums[l] <= target < nums[mid]、右半用 nums[mid] < target <= nums[r]——mid 本身已经在循环开头和 target 比过、确认不相等，所以范围要把 mid 排除、把端点含进来。循环条件必须是 l <= r，写成 l < r 会在区间只剩一个元素时漏查、误报 -1。另外，若数组允许重复元素（LeetCode 81），nums[l] 等于 nums[mid] 时判不出哪半有序，只能逐格收缩，最坏退化到 O(n)——本题保证无重复，才有稳定的对数复杂度。

Python

def search(nums, target):
    l, r = 0, len(nums) - 1
    while l <= r:
        mid = (l + r) // 2
        if nums[mid] == target:
            return mid
        if nums[l] <= nums[mid]:        # 左半有序
            if nums[l] <= target < nums[mid]:
                r = mid - 1            # target 在有序左半
            else:
                l = mid + 1
        else:                          # 右半有序
            if nums[mid] < target <= nums[r]:
                l = mid + 1            # target 在有序右半
            else:
                r = mid - 1
    return -1

C++

int search(vector<int>& nums, int target){
    int l = 0, r = nums.size() - 1;
    while(l <= r){
        int mid = l + (r - l) / 2;
        if(nums[mid] == target) return mid;
        if(nums[l] <= nums[mid]){          // 左半有序
            if(nums[l] <= target && target < nums[mid]) r = mid - 1;
            else l = mid + 1;
        } else {                           // 右半有序
            if(nums[mid] < target && target <= nums[r]) l = mid + 1;
            else r = mid - 1;
        }
    }
    return -1;
}

Java

public int search(int[] nums, int target) {
    int l = 0, r = nums.length - 1;
    while (l <= r) {
        int mid = l + (r - l) / 2;
        if (nums[mid] == target) return mid;
        if (nums[l] <= nums[mid]) {            // 左半有序
            if (nums[l] <= target && target < nums[mid]) {
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        } else {                              // 右半有序
            if (nums[mid] < target && target <= nums[r]) {
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
    }
    return -1;
}