如何用二分查找旋转排序数组的最小值？为什么和 a[hi] 比较？

简化版

旋转排序数组的最小值就在旋转点处。用二分:拿 a[mid] 和右端点 a[hi] 比较——a[mid] > a[hi] 说明最小值在 mid 右边(lo = mid+1);a[mid] < a[hi] 说明最小值在 mid 左边或就是 mid(hi = mid)。收敛后 a[lo] 就是最小值。关键是和 a[hi] 比,不和 a[lo] 比——和 a[lo] 比无法区分「整体有序」和「已旋转」两种情况。

详细版

int findMin(int[] a) {
    int lo = 0, hi = a.length - 1;
    while (lo < hi) {                    // 注意是 <，收敛到单个元素
        int mid = lo + (hi - lo) / 2;
        if (a[mid] > a[hi]) lo = mid + 1;  // 最小值在右半（mid 右边）
        else hi = mid;                      // a[mid] < a[hi]，最小在左半（含 mid）
    }
    return a[lo];   // lo == hi，指向最小值
}

和 a[hi] 比:a[mid] > a[hi] → mid 在旋转点左段(较大值那段),最小值在右边,lo = mid+1。
a[mid] < a[hi] → mid 在旋转点右段(较小值那段)或就是最小值,hi = mid(保留 mid)。
循环 lo < hi,退出时 lo == hi 指向最小值。

完整版教学

一、最小值在哪:旋转点

旋转排序数组由旋转点分成两段:前段(较大值)和后段(较小值),前段所有值都 > 后段所有值。最小值就是后段的第一个元素,即旋转点。比如 [4,5,6,7,0,1,2],最小值 0 在下标 4(旋转点)。所以问题转化为「用二分找到这个旋转点」。

二、核心:和右端点 a[hi] 比较

判断 mid 落在前段(大)还是后段(小),最可靠的参照是右端点 a[hi]:

a[mid] > a[hi]:a[mid] 比右端还大,说明 mid 在前段(较大的那段),最小值(旋转点)一定在 mid 右边,所以 lo = mid + 1(mid 本身不可能是最小值,排除)。
a[mid] < a[hi]:a[mid] 比右端小,说明 mid 在后段(较小的那段),最小值在 mid 左边或就是 mid,所以 hi = mid(保留 mid,它可能就是答案)。

这样每步都能确定最小值在哪半,O(log n) 收敛。

三、为什么不和 a[lo] 比较(关键)

这是本题最容易踩的坑。如果拿 a[mid] 和左端点 a[lo] 比,会出问题:

考虑 [1, 2, 3, 4, 5]（没旋转，或旋转了 n 次）：
a[mid] = 3 > a[lo] = 1 → 会误判「最小值在右半」
但实际最小值 1 在左边！

问题在于:和 a[lo] 比时,无法区分「数组整体有序(最小在最左)」和「发生了旋转(最小在右段)」这两种情况——两种情况下 a[mid] 都可能 > a[lo]。而和 a[hi] 比就没有这个歧义:整体有序时 a[mid] < a[hi](会正确往左收),旋转时才可能 a[mid] > a[hi]。所以和右端点比更可靠,这是旋转数组找最小值的定式。

四、为什么循环条件是 lo < hi 而不是 lo <= hi

这题用 while (lo < hi),收缩用 hi = mid(不是 mid-1)。原因:我们要收敛到唯一的最小值位置,而不是「找到就返回」。lo < hi 保证退出时 lo == hi 恰好指向那一个元素;如果写 lo <= hi 且 hi = mid,当 lo == hi 时 mid 还等于 lo,hi = mid 不变,会死循环。所以「hi = mid 配 while lo < hi」是这类「找位置」二分的标准搭配。

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

若数组有重复(LeetCode 154),a[mid] == a[hi] 时无法判断最小值在哪半(比如 [3,3,1,3])。处理:a[mid] == a[hi] 时只能 hi--(去掉一个重复的右端点,不影响最小值的存在),此时最坏退化到 O(n)。注意这里是 hi-- 而不是 hi = mid-1(避免跳过最小值)。

六、复杂度与姊妹题

时间 O(log n)(无重复);有重复最坏 O(n)。
姊妹题:「旋转数组查找目标值」(和 a[lo]/a[mid] 配合判断哪半有序);找最小值是先决步骤之一。找到最小值(旋转点)后,还能把数组「还原」成两段有序,再在对应段做普通二分。

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

算法正确性的核心不是记住某个 while，而是始终维护这个不变量：最小值始终位于 [lo,hi]；与 a[hi] 比较可判断 mid 是否在左段。

对应的状态推进是：a[mid]>a[hi] 时最小值在 mid 右侧，否则 mid 仍可能是最小值。每次推进前都应能解释“为什么被排除的部分不可能再包含答案”，否则只是碰巧通过样例。

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

复杂度不能只背一个符号。无重复时 O(log n)；有重复且 a[mid]==a[hi] 时 hi— 最坏 O(n)。

带数字走一遍：[4,5,6,1,2,3] 中 mid=6>3，直接把 lo 移到 mid+1。手算时要同时记录下标、区间含义和本轮排除的候选，才能暴露等号与边界错误。

核对项	结论
前提	数组必须由非降序数组旋转得到
时间复杂度	无重复 O(log n)，重复最坏 O(n)
额外空间	O(1)
关键边界	lo<hi 保证 mid<hi；重复值让所属分段无法唯一判断
替代方案	若还要找目标值，使用旋转数组搜索的有序半区逻辑

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

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

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

八、常见误区与追问

误区：只要记住模板就适用于所有输入。 本题成立的前提是“数组必须由非降序数组旋转得到”，前提被破坏后必须换算法或重新证明。
误区：复杂度只写无重复 O(log n)，重复最坏 O(n) 就算完整。 还要说明输入参数、预处理、递归栈以及最坏退化条件；本题的推导是“无重复时 O(log n)；有重复且 a[mid]==a[hi] 时 hi— 最坏 O(n)”。
误区：重复值和边界值不会改变代码。 lo<hi 保证 mid<hi；重复值让所属分段无法唯一判断。
追问：为什么每次推进不会漏掉答案？ 因为始终维护“最小值始终位于 [lo,hi]；与 a[hi] 比较可判断 mid 是否在左段”，被舍弃区域已由顺序或状态关系证明不可能更优。
追问：用一个数字例子怎么讲？ 可以从“[4,5,6,1,2,3] 中 mid=6>3，直接把 lo 移到 mid+1”开始，逐轮写出状态与被排除区间。
追问：什么时候不该使用这个方案？ 当前提不满足或退化代价不可接受时，应考虑“若还要找目标值，使用旋转数组搜索的有序半区逻辑”。
追问：如何设计自测避免只过样例？ 同时覆盖最小规模、重复值、极端分布、无解/边界解，并对关键状态加断言。

九、加强记忆

旋转数组最小值 = 旋转点。二分和右端点 a[hi] 比:a[mid] > a[hi] → 最小在右(lo=mid+1);a[mid] < a[hi] → 最小在左或就是 mid(hi=mid,保留)。必须和 a[hi] 比不和 a[lo] 比——和 a[lo] 比无法区分「整体有序」和「已旋转」。用 while lo<hi + hi=mid(防死循环)。有重复时 a[mid]==a[hi] 只能 hi--,最坏 O(n)。

简化版

详细版