如何用二分查找峰值元素？无序数组为什么也能二分？

简化版

峰值元素是比它左右相邻都大的元素(数组两端外视为负无穷)。神奇的是,即使数组无序也能二分:比较 a[mid] 和 a[mid+1]——如果 a[mid] < a[mid+1],说明右边在上升,右边一定存在峰值,往右找;否则往左找(含 mid)。像爬坡,始终朝更高的方向走,一定能到达一个峰顶。O(log n)。

详细版

int findPeakElement(int[] a) {
    int lo = 0, hi = a.length - 1;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (a[mid] < a[mid + 1]) lo = mid + 1;  // 右边在上升，峰在右侧
        else hi = mid;                           // a[mid] >= a[mid+1]，峰在左侧或就是 mid
    }
    return lo;   // lo == hi，指向一个峰值
}

比较 a[mid] 和 a[mid+1](相邻两个),判断当前在「上坡」还是「下坡」。
上坡(a[mid] < a[mid+1]):峰值在右边,lo = mid+1。
下坡或平/峰(a[mid] >= a[mid+1]):峰值在左边或就是 mid,hi = mid。
题目通常保证相邻元素不相等,所以不用处理相等。

完整版教学

一、峰值问题:无序也能二分

一般认为二分只适用于有序数组,但寻找峰值(LeetCode 162)打破了这个印象——数组无序也能二分。原因是二分的本质不是「有序」,而是「能根据 mid 的信息,确定答案在哪一半、从而排除另一半」。峰值问题里,虽然整体无序,但通过「mid 和相邻元素的高低关系」,就能判断「哪个方向一定存在峰值」,于是照样能二分。理解这点,能大大拓宽二分的应用面。

二、核心:爬坡思想

把数组想象成一条高低起伏的山路,峰值就是山顶。站在 mid 位置,看它和右邻居 a[mid+1]:

a[mid] < a[mid+1](右邻更高,当前在上坡):沿着上坡往右走,右边一定有个峰顶(要么一直升到右边界——右边界外是负无穷,所以右边界本身也可能是峰;要么升到某处开始下降,那个转折就是峰)。所以峰值一定在右边,lo = mid+1。
a[mid] >= a[mid+1](右邻更低,当前在下坡或就在峰上):往左走,左边一定有峰(同理,要么升到左边界,要么 mid 本身就是峰)。所以峰值在左边或就是 mid,hi = mid(保留 mid)。

只要始终朝「更高」的方向走,必然能爬到一个峰顶。 这就是爬坡思想。

三、为什么一定存在峰值、且能找到

数组两端之外视为负无穷。所以不管数组怎么起伏,从任意位置朝「上升」方向一直走,不可能无限上升(数组有限、边界外是负无穷),必然会遇到一个「开始下降」的点或走到边界——那就是峰值。二分每次朝上升方向排除一半,logn 步后收敛到一个峰值。注意:数组可能有多个峰,二分找到的是其中任意一个(题目只要求返回任一峰值)。

四、为什么 mid+1 不会越界

循环条件是 while (lo < hi),所以进入循环时 lo < hi,即 mid = lo + (hi-lo)/2 < hi,于是 mid + 1 <= hi 不会越界。这是「比较 mid 和 mid+1」型二分的一个细节:用 lo < hi 保证 mid 严格小于 hi,mid+1 才安全。如果写成 lo <= hi 就可能 mid == hi、mid+1 越界。

五、和「山脉数组」的联系

本题(找峰值):数组任意起伏、可能多峰,找任一峰值,a[mid] vs a[mid+1] 定方向。
山脉数组找峰顶(LeetCode 852):数组保证先严格递增再严格递减(单峰),找唯一峰顶,方法完全一样。
山脉数组找目标值:先二分找峰顶,把数组分成「递增段」和「递减段」,再在对应段做普通二分。

它们都是「用相邻元素比较定方向」的二分,是「无序/单调段」二分的一类。

六、复杂度与要点

时间 O(log n):每步排除一半。
要点:比较 a[mid] 与 a[mid+1] 定「上坡/下坡」,朝上坡方向走;while lo < hi + hi = mid 收敛且保证 mid+1 不越界;找到的是任意一个峰。

峰值二分不依赖数组整体有序，而依赖“沿坡向至少存在一个峰”的局部单调结论。若题目改成返回所有峰值或全局最大值，排除一半将不再满足输出要求，此时通常需要线性扫描。

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

算法正确性的核心不是记住某个 while，而是始终维护这个不变量：根据 a[mid] 与 a[mid+1] 的坡向，总能保留至少一个峰值所在半区。

对应的状态推进是：上坡时舍弃左侧到 mid，下坡时保留 mid 并舍弃右侧。每次推进前都应能解释“为什么被排除的部分不可能再包含答案”，否则只是碰巧通过样例。

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

复杂度不能只背一个符号。区间每轮减半，时间 O(log n)。

带数字走一遍：[1,3,5,4,2] 在 5 左侧上坡、右侧下坡，最终收敛到下标 2。手算时要同时记录下标、区间含义和本轮排除的候选，才能暴露等号与边界错误。

核对项	结论
前提	题目通常把边界外视为负无穷且只要求任意峰值
时间复杂度	O(log n)
额外空间	O(1)
关键边界	循环用 lo<hi，因而 mid<hi，访问 mid+1 安全；平台定义可能要求严格峰值
替代方案	若要求全局最大值可直接扫描，若是标准山脉数组同样可二分

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

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

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

八、常见误区与追问

误区：只要记住模板就适用于所有输入。 本题成立的前提是“题目通常把边界外视为负无穷且只要求任意峰值”，前提被破坏后必须换算法或重新证明。
误区：复杂度只写 O(log n) 就算完整。 还要说明输入参数、预处理、递归栈以及最坏退化条件；本题的推导是“区间每轮减半，时间 O(log n)”。
误区：重复值和边界值不会改变代码。 循环用 lo<hi，因而 mid<hi，访问 mid+1 安全；平台定义可能要求严格峰值。
追问：为什么每次推进不会漏掉答案？ 因为始终维护“根据 a[mid] 与 a[mid+1] 的坡向，总能保留至少一个峰值所在半区”，被舍弃区域已由顺序或状态关系证明不可能更优。
追问：用一个数字例子怎么讲？ 可以从“[1,3,5,4,2] 在 5 左侧上坡、右侧下坡，最终收敛到下标 2”开始，逐轮写出状态与被排除区间。
追问：什么时候不该使用这个方案？ 当前提不满足或退化代价不可接受时，应考虑“若要求全局最大值可直接扫描，若是标准山脉数组同样可二分”。
追问：如何设计自测避免只过样例？ 同时覆盖最小规模、重复值、极端分布、无解/边界解，并对关键状态加断言。

九、加强记忆

峰值 = 比左右相邻都大(两端外视为负无穷)。无序也能二分——因为二分本质是「能判断答案在哪半」,不必真有序。爬坡思想:比较 a[mid] 与 a[mid+1],上坡(a[mid]<a[mid+1])则峰在右(lo=mid+1)、下坡或在峰(>=)则峰在左或就是 mid(hi=mid)。始终朝更高方向走必达峰顶,O(log n)。用 while lo<hi 保证 mid+1 不越界。找到的是任一峰。

简化版

详细版