无序数组二分找峰值：从方向信号到O(log n)工程实践

二分法寻找峰值实战复盘：无序数组里高效定位峰值的核心技巧

第一次碰到“二分法寻找峰值”这道题，我下意识觉得出题人在为难人——二分查找不是明摆着要求数组有序吗？一个彻底无序的数组，凭什么能二分？直到我把“有序”这个词拆开看，才发现自己一直把二分理解窄了。二分真正依赖的不是“整体有序”，而是“每次比较都能排除掉一半候选区间”这个性质。峰值问题恰好满足：虽然数组乱成一团，但任意位置往左往右走，总能靠一步比较判断出“上坡”在哪边，而上坡的尽头必然是一个峰值。

所以这篇内容想聊的不是一道算法题的八股解法，而是二分法寻找峰值这件事背后的思考方式：它解决的是在无序数组中高效定位峰值的问题，把线性扫描的 O(n) 压到 O(log n)。适合三类人看：刚学完二分模板、只会套有序数组的新手；面试前想搞清楚“为什么能二分”怎么讲清楚的求职者；以及手上有时间序列、波形数据、需要找局部极值的工程同学。我会把峰值定义、正确性论证、三种区间写法、踩过的死循环和越界坑，一次性摊开讲。

1. 先把“峰值”这个词定义清楚：边界条件是第一步

1.1 峰值的判定标准与边界约定

很多人代码写错，不是二分写错了，是峰值定义没想明白。标准定义很干脆：一个元素nums[i]是峰值，当且仅当它严格大于左右两个邻居，即nums[i] > nums[i-1]且nums[i] > nums[i+1]。问题来了——数组的第一个元素没有左邻居，最后一个元素没有右邻居，怎么办？

工程上通行的约定是：把数组两端想象成各有一个负无穷大的哨兵。也就是nums[-1] = nums[n] = -∞。这样一来，首元素只要大于第二个元素，它就是峰值；尾元素只要大于倒数第二个元素，它就是峰值。这个约定看着像作弊，其实非常实用，因为它保证了一件事：任何非空数组至少存在一个峰值。单元素数组，它自己就是峰值。

我见过不少人纠结“万一有多个峰值返回哪个”——这题的通常约定是返回任意一个即可。这一点很关键，因为后面的算法正是利用“返回任意一个”这个宽松条件，才能只往一边走、不做回溯。如果题目要求返回所有峰值或者最大峰值，那就完全是另一道题了，二分不一定还成立。所以读题时先确认三件事：是否严格大于、端点怎么算、返回任意一个还是特定一个。

1.2 为什么暴力扫描是最笨但最该先写的版本

在动手二分之前，我一定会先写一版暴力解法。不是为了交差，是为了当“标准答案”。峰值问题的暴力解法就是从头扫一遍，逐个比较相邻元素，复杂度 O(n)，代码三五行的样子。它的价值在于：二分写挂了、死循环了、答案对不上时，我可以拿暴力版去跑随机数组做对拍。

具体的对拍套路很土但极有效：写一个随机数组生成器，长度从 1 到 20 随机，元素值随机，然后循环几百次，把二分返回的下标拿去做峰值校验（检查它是否满足定义），一旦不满足就打印数组和返回值。我在这上面抓到过至少两次自己以为是“样例特判”的问题，实际是区间收缩写反了。

注意：校验函数一定要按定义严格写，包括端点哨兵的处理。我见过有人校验函数自己写错，导致明明正确答案被判成错误，白折腾一晚上。

1.3 无序数组里藏着的“隐秩序”

这是整篇文章最想让你带走的一句话：无序数组里也有秩序，只是这个秩序不是全局的，是局部的、方向性的。

具体说，相邻两个元素的比较nums[i] vs nums[i+1]，给出的是一个方向信号：上坡还是下坡。这个信号虽然不能告诉你全局最大值在哪，但它能告诉你一件确定的事——沿着上坡方向走，一定能遇到一个峰值，因为数组是有限的，不可能无限上坡，总得有个地方开始下坡，那个转折点就是峰值。

这个性质用生活化的说法：你在连绵的山地里走，眼前一片雾，只看得到脚下这一步是往上还是往下。你不需要知道最高峰在哪，只要一直往上走，最终一定会站在某个山顶上。这就是“局部信息足以支撑正确决策”的典型场景，也是二分能成立的土壤。

1.4 二分能用在无序数组上的真正前提

教科书上说“二分查找要求数组有序”，这句话其实是个简化版结论。更本质的说法是：只要你有一个判定条件，能证明答案在某一半区间里必然存在，你就可以砍掉另一半。

有序数组里，nums[mid] < target就能判定答案在右半，这是单调性给的。峰值问题里，nums[mid] < nums[mid+1]就能判定右半区间必然含峰值，这是“上坡必有顶”给的。两者的共同点是：判定条件保证被砍掉的区间里绝对没有答案，或者至少保留的区间里绝对有答案。

这里有个容易踩的思维坑：很多人以为要保证“答案唯一”才能二分。其实不需要。峰值问题里数组可能有多个峰值，但只要我能保证“当前区间内至少存在一个峰值”，并且每次收缩都不把它弄丢，二分就成立。这就是为什么返回“任意一个”的条件如此重要——它把“必须找到唯一解”降级成了“必须不弄丢至少一个解”，难度直降。

2. 核心逻辑拆解：把“找峰值”偷换成“找上坡方向”

2.1 一次比较能砍掉一半的推理过程

假设当前搜索区间是[left, right]，取中点mid。此时比较nums[mid]和nums[mid+1]，只有两种情况。

第一种，nums[mid] < nums[mid+1]，说明从 mid 到 mid+1 是上坡。那么从 mid+1 出发一直往右走，要么一路向上直到数组末尾（此时末尾元素是峰值，因为右哨兵是负无穷），要么中途某处开始下降，那个转折点就是峰值。两种情况都说明：右半区间[mid+1, right]里必然存在至少一个峰值。于是可以把 left 挪到 mid+1，左半部分连同 mid 一起扔掉。

第二种，nums[mid] > nums[mid+1]，说明从 mid 到 mid+1 是下坡。那么从 mid 出发往左走，同理，要么一路向上到首元素（首元素即峰值），要么中途转折，总之左半区间[left, mid]里必然存在峰值。于是把 right 挪到 mid，右半部分扔掉。

关键在于mid归属哪一边。注意第二种情况里我把right = mid而不是mid - 1，因为mid自己就是候选——它是下坡的起点，很可能就是那个峰顶。如果写成right = mid - 1，就把候选自己排除了，可能直接漏掉答案。这是最常见的错误之一，后面第 4 节会专门展开。

2.2 用循环不变式把“不会走丢”钉死

想真正说服自己（以及面试官）这个算法是对的，最靠谱的工具是循环不变式。我给它定义成一句话：在每一轮循环开始时，闭区间[left, right]内至少存在一个峰值。

初始化：left = 0, right = n-1，整个数组至少有一个峰值，成立。

保持：按 2.1 的推理，无论走哪个分支，新区间都保留了一个峰值，成立。

终止：循环条件是left < right，退出时left == right，区间收缩成一个点。既然区间内至少有一个峰值，而这个区间只有一个元素，那它必然是峰值。所以返回left一定正确。

这个论证链条短得惊人，但它解释了为什么代码只需要四五行。我建议每个学这题的人都手写一遍这个不变式，因为在面试里被追问“你怎么证明”的时候，能把这个说清楚，比背模板强太多。真实场景里，工程师信不信你的方案，往往就取决于你能不能说清“它为什么不会错”。

2.3 二分找峰值和二分找最大值的区别

这里必须澄清一个高频混淆点：峰值不等于最大值。峰值只需要比邻居大，局部最大即可；最大值是全局最大。这两个问题难度完全不同。

在普通的无序数组里找全局最大值，你没有任何办法跳过元素，必须全看一遍，O(n) 是下界，二分救不了你。但找“任意一个局部峰值”，你可以靠方向信号做跳跃，因为局部性质是局部的，不用看全局。

有意思的是，如果数组是“单峰”的（先严格递增再严格递减，形如山脉数组），那峰值就是最大值，这时候二分找峰值等价于二分找最大值，nums[mid] < nums[mid+1]就往右，反之往左，和上面代码一模一样。所以你可以把单峰数组看成峰值问题的一个特例。理解了这个包含关系，很多变体题就不会混了：山脉数组找顶峰、旋转数组找最小值、找峰值，这些题的二分骨架是同一套，区别只在判定条件。

2.4 严格大于这个条件为什么不能随便放宽

上面所有推理都建立在“严格大于”上。如果允许nums[i] >= nums[i-1] && nums[i] >= nums[i+1]（即允许平台），情况立刻变复杂。

考虑数组[1, 2, 2, 2, 1]。中间那三个 2 都是峰值（如果按非严格定义），但nums[mid] > nums[mid+1]这个判定在mid=2时会失败（2 不大于 2），代码会往右走，仍然能找到峰值，看起来没事。但换成[2, 1, 2]这种，中间是谷，两端是峰，代码也能找到。真正出问题的是某些特定的平台结构，比如[1, 2, 2, 1]里查找，如果 mid 落在平台中间，比较结果相等，走“往右”分支，答案是找到了，但如果你需要返回“最左边的峰值”或者“平台的左端点”，这个走法就不保证。

我的做法是：遇到带平台的变体，先明确题目要什么。如果只是要任意一个峰，上面的代码大多数情况能跑；如果要特定位置的峰，就得改判定条件，比如相等时向左收缩，或者改成找“第一个满足nums[i] > nums[i+1]的位置”。这一步不能凭感觉，必须举反例验证。

3. 手写代码：从标准模板到边界打磨

3.1 Java 版标准模板与逐行注释

public int findPeakElement(int[] nums) { // 约定：nums[-1] = nums[n] = -∞，故非空数组必有峰值 int left = 0; int right = nums.length - 1; // 用 left < right 而非 <=，目的是让区间最终收缩到单点 while (left < right) { // 防溢出写法，等价于 (left + right) / 2 但更安全 int mid = left + (right - left) / 2; if (nums[mid] > nums[mid + 1]) { // mid 处于下坡起点，峰值在 [left, mid] 内，注意保留 mid right = mid; } else { // mid 处于上坡，峰值在 [mid+1, right] 内 left = mid + 1; } } // 退出时 left == right，且区间内保证有峰值，故该点即答案 return left; }

这段代码里，mid + 1会不会越界？不会。因为循环条件保证了left < right，而mid = left + (right-left)/2，当right = left + 1时，mid = left，此时mid + 1 = right <= n-1，安全。这个推导值得单独记下来，因为它省掉了你在循环里加mid + 1 < n的防御判断，代码更干净。

3.2 三种区间写法的对照与取舍

同一道题，区间定义不同，代码长得完全不一样。我整理了一张表，方便你对照自己的习惯选一种，然后死记一种，别混着用。

我个人长期用第一种闭区间写法，原因是它和“区间内必有峰值”这个不变式完全对应，脑子里不需要做额外转换。第三种写法的问题在于r = mid - 1会把 mid 自己排除，而 mid 恰恰可能是峰值——[1, 3, 2]里 mid=1 的值 3 就是峰值，如果你在nums[mid] > nums[mid+1]时写r = mid - 1，直接跳到 0，如果不额外判断就会返回错的下标。这也是为什么我不推荐新手用这种写法。

3.3 Python 版本与单元素、双元素的边界验证

def find_peak(nums): if not nums: raise ValueError("数组不能为空") left, right = 0, len(nums) - 1 while left < right: mid = (left + right) // 2 if nums[mid] > nums[mid + 1]: right = mid else: left = mid + 1 return left

拿几个边界跑一遍，心里才踏实。

[1]：left = right = 0，不进循环，返回 0，正确（单元素按约定是峰值）。

[2, 1]：left=0, right=1，mid=0，nums[0]=2 > nums[1]=1，right=0，退出返回 0，正确。

[1, 2]：mid=0，1 < 2，left=1，退出返回 1，正确。

[1, 3, 2]：mid=1，3 > 2，right=1，退出返回 1，正确。

[1, 2, 3, 1]：mid=1，2 < 3，left=2；mid=2，3 > 1，right=2，返回 2，正确。

[3, 2, 1]：mid=1，2 > 1，right=1；mid=0，3 > 2，right=0，返回 0，正确。

这几组跑完，我对模板的信心基本就有了。建议你也照着跑一遍，别嫌简单，边界是这类题唯一真正会翻车的地方。

3.4 二维峰值问题：把一维思路往上抬一层

一维玩熟了，很自然会碰到二维版本：矩阵里找一个元素，它大于上下左右四个邻居。这里的经典做法是“按列二分”：每次取中间那一列，找到该列的最大值所在行row，然后比较matrix[row][mid]和它右边的邻居matrix[row][mid+1]。

如果右边更大，说明存在一条向右的上坡路径，峰值在右半边的列里，left = mid + 1；如果左边更大（或右边更小），峰值在左半边，right = mid。为什么可以这样？因为该列的最大值所在行，上下方向已经不可能更大，只剩左右方向需要判断，一维的那套推理原封不动搬过来即可。

复杂度是 O(n log m)，其中 n 是行数、m 是列数。这个技巧我第一次看觉得很精巧，后来发现它其实就是“把二维问题降到一维再二分”的通用套路——先在一个维度上求极值，把另一个维度消掉，剩下的就是标准一维问题。

4. 踩坑实录：那些让我半夜还在调死循环的问题

4.1 死循环的三种常见成因

第一种，while (left <= right)配left = mid。当left = mid且right = mid + 1时，mid还是left，区间不变，无限循环。修法是把循环条件改成left < right，或者把收缩改成left = mid + 1。

第二种，mid取整方向搞错。mid = (left + right + 1) / 2（向上取整）配right = mid，在某些相邻区间会卡住。取整方向和收缩方式必须匹配：向下取整配right = mid安全，向上取整配left = mid安全。这条规律我写在便签上贴过很久。

第三种，mid计算溢出。left + right在超大数组上会溢出成负数，导致下标异常。改成left + (right - left) / 2就没事，这个习惯在 Java 和 C++ 里一定要养成。

提示：写二分时先在纸上画一个长度为 2 的区间，把代码“手动执行”一遍。长度为 2 是死循环的高发区，90% 的死循环都能在这一步暴露。

4.2 越界与空数组的防御处理

mid + 1越界是最容易疏忽的。在标准闭区间写法里它是安全的，但很多人为了“保险”把初值写成right = nums.length，变成左闭右开，这时候mid + 1就等于n，直接抛异常。

另一个是空数组。题目通常保证n >= 1，但工程代码里最好显式判断。我自己的习惯是入口处加一行if (nums == null || nums.length == 0) return -1;，语义清晰，也避免调用方传脏数据。

还有一个隐蔽的坑：在 C++ 里用vector<int>判断相邻元素时，如果传进来的是空 vector，即使你在函数开头判断了 size，后面调用nums.size() - 1会得到无符号数的极大值，right变成一个巨大的数，取 mid 时直接越界。修法是先判断空再算right，或者把 size 转成int。

4.3 常见问题速查表

4.4 对拍与随机测试：比背模板更值钱的习惯

我所有二分代码上线前都会做随机对拍，这套流程值得抄：写一个暴力函数bruteForce(nums)扫出所有满足定义的下标，返回其中一个；再写一个校验函数isValid(nums, idx)检查返回的下标是否真满足峰值定义（端点按哨兵规则处理）；最后写 500 轮随机测试，长度 1 到 30，值域 -100 到 100。

这套流程抓 bug 的效率高得离谱。我曾经写了一个“看起来完全没问题”的版本，对拍到第 37 轮时数组[5, 4, 4, 5]失败了——原因是相等的元素让判定走了另一边，虽然最终答案碰巧还对，但对拍暴露出返回的下标不满足我预期的“最左峰值”。如果没有对拍，这个问题会一直藏在代码里，直到线上出现异常数据。

5. 复杂度分析与工程落地的真实考量

5.1 为什么 O(log n) 在这里有意义

单看n = 1000，线性扫描和二分都很快，差距感觉不出来。但当你在做实时信号处理，每秒要在百万级采样点上找局部极值，O(n) 和 O(log n) 的差别就是能不能跑满帧率的问题。我在处理一段连续波形数据时遇到过这个场景：需要在一帧 200 万点的数据里定位若干局部峰值来触发事件判断，线性扫一遍约几毫秒，看起来不多，但这个逻辑每秒触发 60 次，叠起来就是可观的 CPU 占用。改成二分之后，单次查找的耗时可忽略。

再说空间复杂度，递归版本 O(log n) 栈空间，迭代版本 O(1)，工程上首选迭代，没有争议。

5.2 工程里真正该注意的事：峰值查找的前提校验

算法题里数组是干净的，工程里不是。真实数据往往带噪声、带缺失、带平台段。直接套二分会出问题，因为“上坡必有顶”这个性质依赖数组是有限且连续的，如果数据被插入了无效值或者存在大段相等值，判定信号就失真了。

我的做法是分两步：先做数据清洗，把无效值剔除或前向填充，平滑掉平台段（比如把相等段压缩成一个点）；再在清洗后的序列上找峰值。如果业务要求必须定位到原始下标，就维护一个清洗前后下标的映射表。

还有一个常被忽略的点：先确认“是否存在峰值”。理论上非空数组必有峰，但这是在哨兵约定下成立的。如果业务上不允许端点算峰值，或者数据被某种约束强制成了单调序列，就可能一个峰都没有。我的习惯是加一个前置判断，扫描一次首尾趋势，或者在二分结束后做一次定义校验，校验不过就返回“无峰值”而不是硬塞一个结果。

5.3 面试里怎么把这件事讲明白

面试聊这题，我最推荐的表达顺序是三步：先讲定义和哨兵约定，明确“至少存在一个峰值”；再讲方向信号，“比较 mid 和 mid+1，上坡方向必有峰”；最后讲为什么每次都对，用区间不变式收尾。这三步讲完，面试官通常不会再追问正确性。

如果被追问“为什么不排序再找”，答案是排序 O(n log n) 更慢，而且峰值问题不需要全局顺序，只要局部方向。如果被追问“能不能找所有峰值”，答案是能，但那就退化成 O(n) 扫描了，二分只保证找到一个。

我还遇到过被问“这个思路还能用在哪”。我当时的回答是：所有“有方向信号、能保证不丢解”的场景都能套。比如在一个序列里找第一个满足某单调性质的位置、在旋转数组里找最小值、在函数上找极值点，骨架是一样的，换的只是判定条件。

6. 从一维到变形的推广：这套思路还能怎么用

6.1 旋转数组找最小值：同一套骨架换判定

旋转数组[4,5,6,7,0,1,2]找最小值，很多人背模板，其实它的骨架和峰值问题同源：比较nums[mid]和nums[right]，如果nums[mid] > nums[right]，说明最小值在右半边，left = mid + 1；否则right = mid。区间的“至少保留一个正确答案”不变式，和找峰值是一模一样的。

我建议把这两道题放在一起学，因为它们的共同点能帮你抓住二分的本质，而不是记一堆互不相干的模板。判定条件怎么选，取决于你想利用什么性质；收缩怎么选，取决于候选是否可能落在被砍掉的那一半。这两句话能覆盖绝大多数二分变形。

6.2 时间序列找局部极值：一个真实的处理流程

假设手上一段传感器读数，需要找出所有“由升转降”的转折点。我的处理流程是：先平滑，去掉高频抖动；再做差分，把序列变成diff[i] = x[i+1] - x[i]；然后在差分序列上找“由正转负”的位置，这些位置就是原始序列的局部峰值。

这个转化非常有用，因为它把“找峰值”变成了“找符号变化点”，而符号变化点可以用二分快速定位（前提是差分序列在某段上单调）。如果整段数据不单调，就分段二分，或者用分治：把序列劈成两半，分别找，再比较交界处的峰值，这是 O(n) 的做法，但常数比全扫小。

注意：真实数据里经常出现“差分为 0”的平台段，这时候符号变化点不唯一，需要业务上明确定义“平台段的左端点算峰还是右端点算峰”。这一步没有标准答案，必须和下游使用方对齐，否则定位出来的时间点会漂移几毫秒，对事件判定影响很大。

6.3 一些容易忽略的实操心得

写这类代码多了，攒了几条不成文但很有用的习惯，分享出来。

第一条，函数入口处永远先处理退化情况：空、单元素、两元素。这三类占了我调试时间的七成以上，提前处理掉，主逻辑会清爽很多。

第二条，循环里别用<=，除非你能把收缩关系推清楚。left < right的语义是“区间还没缩成一个点”，直观、好推、不易错，我几乎只用这种。

第三条，把“区间内有答案”写成注释放在循环上面。这不是为了好看，是为了在改代码时随时提醒自己：任何收缩都不能把候选弄丢。我改代码改出 bug 的时候，八成都是忘了这条。

第四条，验证永远用定义验证，不要用“和预期输出一致”验证。因为峰值可能不止一个，标准答案说不定和你返回的不是同一个，但都是对的。

最后分享一个我常用的小技巧：如果你对某个二分的收缩方式不确定，就把区间长度缩到 2，手动走一遍。长度 2 的区间只有left和right两个位置，mid一定等于left，此时mid + 1 == right，走哪个分支、区间变成什么样，一目了然。我把这个叫“两点检验法”，它帮我抓出来的死循环和漏候选问题，比我读十篇文章都管用。