如何在旋转排序数组中用二分查找一个目标值？

简化版

旋转排序数组(如 [4,5,6,7,0,1,2])整体不有序,但用 mid 一分为二后,至少有一半是有序的。做法:每次判断「左半 [lo,mid] 有序还是右半 [mid,hi] 有序」,再看 target 是否落在那个有序半的范围内——在就往那半收,不在就往另一半收。这样仍能 O(log n) 定位。关键是每步先找出有序的那一半,再判断 target 在不在其中。

详细版

int search(int[] a, int target) {
    int lo = 0, hi = a.length - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (a[mid] == target) return mid;
        if (a[lo] <= a[mid]) {                 // 左半 [lo, mid] 有序
            if (a[lo] <= target && target < a[mid]) hi = mid - 1; // target 在左半
            else lo = mid + 1;                                    // 否则去右半
        } else {                                // 右半 [mid, hi] 有序
            if (a[mid] < target && target <= a[hi]) lo = mid + 1; // target 在右半
            else hi = mid - 1;                                    // 否则去左半
        }
    }
    return -1;
}

判断哪半有序:a[lo] <= a[mid] 成立说明左半有序,否则右半有序(旋转点在左半)。
判断 target 在不在有序半:用有序半的两个端点值夹一下 target。
在有序半就收到那半,不在就去另一半。

完整版教学

一、旋转排序数组是什么

一个升序数组从某个点「旋转」——把前面一段挪到后面。比如 [0,1,2,4,5,6,7] 从下标 4 旋转成 [4,5,6,7,0,1,2]。它的特点是:整体不再有序,但由一个「断崖」(旋转点)分成两段各自有序的部分,且前一段的所有值都大于后一段。要在这种数组里 O(log n) 查找,不能直接二分,得处理这个断崖。

二、核心洞察:mid 两侧至少一半有序

关键观察:无论旋转点在哪,用 mid 把数组切成两半,其中至少有一半是完全有序的(旋转点只能落在一半里,另一半必然连续有序)。所以每一步:

先判断哪一半有序。
在有序的那一半里,可以用它的端点值轻松判断 target 在不在其中(有序半可以用范围夹)。
target 在有序半 → 收缩到有序半;不在 → 收缩到另一半(乱序半,但下一轮它又会被分出一个有序半)。

这样每步排除一半,复杂度保持 O(log n)。

三、怎么判断哪一半有序

用 a[lo] 和 a[mid] 比较:

a[lo] <= a[mid]:说明从 lo 到 mid 是连续递增的(没跨过旋转点),左半有序。
否则(a[lo] > a[mid]):说明 lo 到 mid 之间有旋转点(出现了下降),那么右半 [mid, hi] 有序。

判断出有序的一半后,就能用它的两个端点值精确框定 target 的位置。

四、怎么判断 target 在有序半里

对有序的那一半,用它的最小值和最大值(两个端点)夹 target:

若左半有序且 a[lo] <= target < a[mid]:target 在左半,hi = mid-1;否则去右半 lo = mid+1。
若右半有序且 a[mid] < target <= a[hi]:target 在右半,lo = mid+1;否则去左半 hi = mid-1。

注意边界的开闭(<= 还是 <):因为 a[mid] 已经在开头判过不等于 target,所以夹的时候把 mid 那端用严格不等号,避免把 mid 重复算进去。

五、走一个例子

a = [4,5,6,7,0,1,2]，找 target = 0：
lo=0,hi=6, mid=3,a[3]=7≠0
  a[0]=4 <= a[3]=7 → 左半[0,3]有序
  0 在 [4,7) 吗？不在 → 去右半 lo=4
lo=4,hi=6, mid=5,a[5]=1≠0
  a[4]=0 <= a[5]=1 → 左半[4,5]有序
  0 在 [0,1) 吗？在！→ hi=4
lo=4,hi=4, mid=4,a[4]=0==target ✓ 返回 4

六、有重复元素的情况(进阶)

如果数组有重复元素(LeetCode 81),a[lo] == a[mid] 时无法判断哪半有序(比如 [1,0,1,1,1])。处理办法:遇到 a[lo] == a[mid] == a[hi] 时,无法二分,只能 lo++, hi-- 收缩一步(跳过重复),此时最坏退化到 O(n)。这是重复元素带来的额外代价,面试常追问。

七、复杂度与要点

时间 O(log n)(无重复);有重复最坏 O(n)。
要点:每步先判哪半有序(a[lo] <= a[mid]),再用有序半端点夹 target 决定去哪半;注意夹的边界开闭(mid 端用严格不等)。

O(log n) 的保证来自无重复值时每轮都能确认一个有序半区。若 a[lo] == a[mid] == a[hi]，无法判断旋转点在哪一侧，只能缩端点消歧，像 [1,1,1,1,0,1] 这样的输入会退化为 O(n)。

八、把不变量、推演与工程边界落到代码上

算法正确性的核心不是记住某个 while，而是始终维护这个不变量：每轮至少有一半仍按原顺序有序，利用其端点判断 target 是否落在其中。

对应的状态推进是：先判断哪半有序，再用包含关系选择保留该半或另一半。每次推进前都应能解释“为什么被排除的部分不可能再包含答案”，否则只是碰巧通过样例。

初始化边界与状态
while 尚未结束:
    根据当前状态作出唯一可证明安全的选择
    更新边界、计数或局部结构
    断言不变量仍然成立
返回不变量在终止状态下推出的答案

复杂度不能只背一个符号。无重复时 O(log n)；重复值可能使判定退化为 O(n)。

带数字走一遍：[4,5,6,7,0,1,2] 中 mid=7，左半有序但 target=0 不在其中，转向右半。手算时要同时记录下标、区间含义和本轮排除的候选，才能暴露等号与边界错误。

核对项	结论
前提	数组须由有序数组旋转；重复值版本需要额外消歧
时间复杂度	无重复 O(log n)，重复最坏 O(n)
额外空间	O(1)
关键边界	半开或闭区间条件必须统一；端点包含关系的等号不可随意改
替代方案	只找旋转点使用与右端点比较的最小值算法

易错点：模板只有在前提和不变量一致时才成立；换了区间定义、重复值规则或输出语义，等号与推进方式就必须重新推导。

实现完成后至少检查五类用例：

空输入或题目允许的最小规模，验证初始化不会越界。
单元素与两个元素，验证循环条件和最后一次推进。
大量重复值，验证相等分支、稳定性或去重语义。
已满足目标性质与极端逆序/偏斜分布，观察最好和退化路径。
上面的数字样例逐轮手算，并与程序记录的状态轨迹逐项对照。

九、常见误区与追问

误区：只要记住模板就适用于所有输入。 本题成立的前提是“数组须由有序数组旋转；重复值版本需要额外消歧”，前提被破坏后必须换算法或重新证明。
误区：复杂度只写无重复 O(log n)，重复最坏 O(n) 就算完整。 还要说明输入参数、预处理、递归栈以及最坏退化条件；本题的推导是“无重复时 O(log n)；重复值可能使判定退化为 O(n)”。
误区：重复值和边界值不会改变代码。 半开或闭区间条件必须统一；端点包含关系的等号不可随意改。
追问：为什么每次推进不会漏掉答案？ 因为始终维护“每轮至少有一半仍按原顺序有序，利用其端点判断 target 是否落在其中”，被舍弃区域已由顺序或状态关系证明不可能更优。
追问：用一个数字例子怎么讲？ 可以从“[4,5,6,7,0,1,2] 中 mid=7，左半有序但 target=0 不在其中，转向右半”开始，逐轮写出状态与被排除区间。
追问：什么时候不该使用这个方案？ 当前提不满足或退化代价不可接受时，应考虑“只找旋转点使用与右端点比较的最小值算法”。
追问：如何设计自测避免只过样例？ 同时覆盖最小规模、重复值、极端分布、无解/边界解，并对关键状态加断言。

十、加强记忆

旋转排序数组查找:整体无序但 mid 两侧至少一半有序。每步:①判哪半有序(a[lo] <= a[mid] → 左半有序,否则右半有序);②用有序半的端点夹 target,在有序半就收到那半、不在就去另一半。O(log n)。有重复元素时 a[lo]==a[mid] 无法判断,只能 lo++/hi-- 收缩,最坏退化 O(n)。找旋转数组最小值是它的姊妹题(和 a[hi] 比较)。

简化版

详细版