无序数组也能二分？LeetCode 162寻找峰值详解

刷题打卡到第125天，碰上了一道值得单独写一篇的题：LeetCode 162，寻找峰值。说实话，我第一次看到这道题的反应和大多数人一样——数组压根没排序，凭什么用二分查找？这不是开玩笑吗？后来把官方题解翻来覆去看了好几遍，又自己动手跑了十几个测试用例，才真正想明白这题的精髓。今天就把这道题的来龙去脉从头到尾讲透：题目规则里藏着什么玄机、无序数组凭什么能用二分、代码模板怎么写才能一次过，以及我实际调试中踩过的几个边界大坑。如果你正在刷二分专题，或者被“峰值”这类问题绕晕过，这篇应该能帮你彻底打通。

1. 峰值到底在找什么：先抠清楚题目规则里的三个细节

1.1 峰值定义：比相邻元素都大，边界元素只看一边

题目给的定义是这样的：峰值元素是严格大于相邻左右邻居的元素。注意“严格大于”这四个字，它意味着不存在相等的情况，这个特性在后面决定二分方向的时候非常重要，后面我会专门讲到。

对于数组中间的某个位置i，成为峰值的条件是：nums[i] > nums[i-1]且nums[i] > nums[i+1]。但是对于数组的第一个元素和最后一个元素，它们只有一边的邻居，所以判断规则变成了：

• 第一个元素：只要nums[0] > nums[1]，它就是一个峰值。
• 最后一个元素：只要nums[n-1] > nums[n-2]，它就是一个峰值。

这个“边界只需比较一边”的规则，是很多人在推导时容易忽略的点。它实际上是题目在暗示我们：数组的边界外侧可以理解成负无穷。换句话说，nums[-1] = nums[n] = -∞。有了这个约定，其实所有位置的判断规则就统一了——每个位置只要比它两侧相邻的元素都大，就是峰值。把边界视为负无穷，是理解后面“峰值必然存在”这一结论的钥匙。

1.2 关键保证：相邻不相等，到底给二分提供了什么

题目里有一句容易被一带而过的话：nums[i] != nums[i+1]，对所有的i都成立。这句话初看只是防止出现歧义，实际上它是整个二分解法成立的前提。

试想一下，如果相邻元素可以相等，比如[1, 1, 1, 1]，那么任何位置都不满足“严格大于邻居”的条件，峰值不存在，题目也就没有唯一解了。再比如[2, 2, 1]，左边第一个 2 和第二 2 相等，无法判断谁更大，二分收缩区间时就会出现不可判定的情况。

所以题目直接在源头把这个“不可判定”的选项堵死了：每一步的比较只存在两种结果，nums[mid] < nums[mid+1]或者nums[mid] > nums[mid+1]。没有第三种情况，这使得我们可以用单个比较就能决定丢掉哪半边区间。

1.3 题目要的是“一个”峰值，不是“最大”的峰值

LeetCode 162 的题目表述是“返回任何一个峰值即可”。这个“任何一个”给解题者松了大绑，也是它能够用二分快速解决的原因之一。因为数组可能同时存在多个峰（比如波浪形数组[1, 3, 2, 4, 1, 5]里，3 和 4 以及 5 都是峰，只要返回其中任意一个的下标就算通过）。

这一点和“找到数组最大值”有本质区别。找最大值必须遍历全数组，因为最大值的定义是全局的，你必须确认某个数比所有数都大才能下结论。而峰值是局部概念，你只需要确认真某个数比它身边的两三个邻居大就够了。局部性意味着我们不需要看完全部数据，这就给“只用对数次比较就能完成搜索”留出了空间。

2. 无序数组为什么也能二分：从“峰值必然存在”说起

2.1 用爬坡模型理解：从左侧出发，一定会遇到峰顶

很多人一提到二分查找，脑子里想到的第一个前置条件就是“数组必须有序”。这个直觉没有错，但它是针对“查找指定目标值”这种场景的。162 这道题要查的不是某个具体的值，而是“位置”，一个具有局部性质的特定位置类型。目标不同，适用的约束自然也不同。

怎么理解无序数组里也能二分？我习惯用一个爬坡的比喻。想象你在一个起伏不平的山脉横截面上行走，山脉的最左端和最右端都通向悬崖，悬崖外是万丈深渊（也就是负无穷）。你现在站在左端点，闭着眼睛往前走，规则是“只要面前是上坡，就继续走”。

• 如果左端点右侧是下坡，那你根本不用走，脚下就是峰顶。
• 如果左端点右侧是上坡，那就往前走。由于整条山脉是有限的，而且终点右侧就是悬崖，这个上升趋势不可能永远持续下去。你总会在某个位置遇到“再往前走就是下坡”的情况，那个位置就是一个峰顶。

所以在这个模型里，峰值一定存在，而且从任意一端出发“顺着上坡走”，一定能走到某个峰顶。这个结论不需要数组有序，只需要边界外是负无穷以及山脉长度有限这两个前提。

2.2 二分只是把爬坡过程加速了：为什么可以放心丢掉一半

爬山模型的结论告诉我们，从左侧出发顺着上坡走一定能找到峰值，但这样一步一步走最坏情况下要遍历整个数组，时间复杂度是 O(n)。二分查找要做的事情，就是给这个爬山过程装上“瞬移”能力——一次跳跃一半的距离。

跳跃的方法是这样的：取区间中点mid，比较nums[mid]和nums[mid+1]。

• 如果nums[mid] < nums[mid+1]，说明mid在爬坡，坡顶在右侧，那整个左半边区间（包括mid）都不可能是峰值所在的一侧，直接丢掉，区间收缩到[mid+1, right]。
• 如果nums[mid] > nums[mid+1]，说明mid在下坡，坡顶在左侧，那整个右半边区间都可以丢掉，区间收缩到[left, mid]。

每次比较都能砍掉一半的搜索空间，这正是二分的本质。整个过程循环下来，区间不断缩小，而且每一步都保证“峰值仍然在我们保留的区间里”，最后剩下的那一个点，就必然是峰值。这种“保证答案不丢”的区间收缩方式，和有序数组二分里“保证目标值不丢”的收缩方式，思路是一模一样的。

2.3 三种特殊形态的数组：全升、全降、单元素

为了验证这个模型，我建议动手把三类特殊情况跑一遍。

第一种是全升数组，比如[1, 2, 3, 4]。这种情况下，最后一个元素就是峰值，因为它大于它唯一的左邻居。二分的过程会一路触发nums[mid] < nums[mid+1]，区间不断右移，最后停在最后一个下标上。

第二种是全降数组，比如[4, 3, 2, 1]。这时候第一个元素就是峰值。二分的过程会一路触发nums[mid] > nums[mid+1]，区间不断左移，最后收敛到下标 0。

第三种是单元素数组，比如[5]。它没有邻居，按题目定义它自己就是峰值。代码里left = right = 0，二分循环根本不会进入，直接返回 0。这三种情况跑通之后，你对这个解法的信心会大很多。

3. 核心洞察：让 mid 和 mid+1 说话，而不是和 target 说话

3.1 比较 nums[mid] 和 nums[mid+1] 的几何含义

普通二分查找里，我们比较的是nums[mid]和目标值target，据此判断“目标在左还是右”。在 162 这道题里，没有target可以比，取而代之的是nums[mid]与nums[mid+1]的大小关系。

这个比较的本质，是在判断当前中点处在“上坡”还是“下坡”的哪一段上。我画了一个非常朴素的示意图来描述这件事：

峰顶 /\ / \ / \ / \ / \ 起点 终点（外侧是负无穷）

当nums[mid] < nums[mid+1]时，中点落在上坡段，方向是向上走的，那么峰顶一定在中点的右侧，左半边全部丢弃。反之当nums[mid] > nums[mid+1]时，中点落在下坡段，说明峰顶在中点的左侧（或者中点自己就是峰顶），右半边丢弃。

这里有一个很容易绕晕的点：nums[mid] > nums[mid+1]是不是意味着mid自己就是峰值？不一定。它只是说明mid处于一个下降沿，真正的峰顶有可能在mid左侧的任意位置，也有可能是mid自己。所以收缩区间时右边界取right = mid，保留mid位置不丢掉，因为在进一步收缩的过程中，mid仍然有可能是最终的答案。

3.2 为什么只和右边比，不比 mid-1 也不比 mid+2

很多初学者会问：判断上坡下坡，为什么只看nums[mid]和nums[mid+1]这一对？也可以看nums[mid-1]和nums[mid]啊，甚至看nums[mid]和nums[mid+2]行不行？

这里面有讲究。看nums[mid]和nums[mid+1]，是题目能保证“必定可比较”的一对相邻元素。如果看nums[mid-1]，当mid = 0时就会发生数组越界访问，你需要额外处理mid是左边界的情况，代码复杂度上升。如果看nums[mid+2]，当mid = n-2时也会越界，而且跳跃地比较两个不相邻的元素，中间可能隔着峰谷，判断出来的上坡下坡方向并不一定是全局趋势，很可能把区间收缩引向错误方向。

所以选择mid和mid+1这一对比较，最大的好处是天然规避了边界判断。在left < right的循环条件下，mid最坏情况取到right - 1，那么mid + 1最多取到right，永远不会越界，不需要额外写if分支。这个细节是让代码保持简洁的关键。

3.3 多峰数组：二分会稳定地找到哪一个峰

当数组里有多个峰值时，二分法的行为值得提前了解，避免在测试时对自己的解法产生怀疑。比如[1, 3, 2, 4, 1, 5, 0]里面，3、4、5 都是峰值。二分法会找到哪个？答案是：取决于中点的位置和每一次比较的方向。

整个收缩过程像是一个“随机但确定”的爬山者——半路被放到某个点，然后一直朝着上坡方向跳跃。最终它收敛到哪个峰，取决于初始区间的中心位置以及每次比较的结果。但这道题不在乎你找到的是哪一个峰，只要求合法即可。所以不需要纠结“为什么我的代码返回了第二个峰而不是第一个峰”，只要返回的那个下标满足峰值定义，就是正确解。

4. 参考实现：while (left < right) 模板的三语言版本

4.1 Python、Java、C++ 的参考解法

先把最常用的写法放出来。这个写法核心是while (left < right)，配合mid = left + (right - left) // 2，然后按上坡方向收缩。Python 版本：

from typing import List class Solution: def findPeakElement(self, nums: List[int]) -> int: left, right = 0, len(nums) - 1 while left < right: mid = left + (right - left) // 2 if nums[mid] < nums[mid + 1]: left = mid + 1 else: right = mid return left

Java 版本：

class Solution { public int findPeakElement(int[] nums) { int left = 0, right = nums.length - 1; while (left < right) { int mid = left + (right - left) / 2; if (nums[mid] < nums[mid + 1]) { left = mid + 1; } else { right = mid; } } return left; } }

C++ 版本：

class Solution { public: int findPeakElement(vector<int>& nums) { int left = 0, right = nums.size() - 1; while (left < right) { int mid = left + (right - left) / 2; if (nums[mid] < nums[mid + 1]) { left = mid + 1; } else { right = mid; } } return left; } };

三份代码的逻辑完全一致。核心就三行：取中点、比较大小、收缩区间。剩下的交给循环自己去收敛。

4.2 循环不变量：每一步都保住“峰一定在区间里”

要理解这段代码为什么正确，不能只看它最终返回了一个数，而是要关注循环不变量。这个版本的循环不变量是：当前区间[left, right]内至少存在一个峰值。

初始时，整个数组[0, n-1]内必然存在峰值（上一节已经证明了），不变量成立。然后看每一步：

• 当nums[mid] < nums[mid+1]时，mid处在上坡段，峰顶不可能在[left, mid]这个左半段里，所以我们把left推到mid + 1，新的区间[mid+1, right]仍然包含至少一个峰，不变量保持。
• 当nums[mid] > nums[mid+1]时，mid处在下坡段，峰顶不可能在[mid+1, right]右半段里，把right收缩到mid，新的区间[left, mid]仍然包含至少一个峰，不变量保持。

既然每一步都保证峰没有丢，且区间长度严格递减，循环必然结束。结束时left == right，此时区间只有一个元素，而既然至少存在一个峰在这个区间里，这个唯一的元素就是峰。这就是整个证明思路，也是面试时你可以直接复述给考官的逻辑链条。

4.3 循环为什么能终止，以及 left 为什么正好落在峰上

还有一个细节值得单独说明：为什么是while (left < right)而不是while (left <= right)？这涉及到mid的计算和right = mid的配合。

在这个模板里，mid = left + (right - left) // 2是向下取整的。当left < right时，mid一定小于right，所以mid + 1一定 ≤right，不会越界。如果写成while (left <= right)，当区间只剩两个元素时，mid == left，如果进入else分支执行right = mid，区间的确会缩短，但也有可能出现right不更新的情况（当left == right时仍进入循环），导致死循环或者需要额外的返回判断。用left < right收敛到一点，代码最干净，也最容易证明正确性。

另外一个自然的问题是：循环结束时为什么left恰好是峰顶？因为收缩过程中，保留的区间始终包含峰，而且数组没有相等相邻元素，所以当区间长度为 1 时，这个唯一元素满足峰值的局部规则。它要么比右边大（因为右边已经因为比较被排除），要么是边界元素只需比左边大，两种情况都成立。

5. 与普通二分查找的区别：排除法和爬坡法是两种思维

5.1 一张表看清两类二分的差异

我整理了下面这张对比表，方便你快速看出普通二分和峰值二分的思维差异：

这张表能看出一个核心差异：普通二分在做“消除法”——每次排除掉不可能包含目标值的一半；峰值二分在做“爬坡法”——每次排除掉不可能包含峰值的一半，但是依据的是“趋势方向”而不是“值的大小”。

5.2 容易混淆的变体：山脉数组峰值、旋转数组最小值

刷到 162 之后，你很快就会遇到一组长相相似但解法微调的题，这里提前帮你做一个区分，省得后面踩坑。

第一类是山脉数组的峰顶索引，比如 LeetCode 852。它的特征是数组先严格递增、后严格递减，只有一个峰。解法一样可以用二分，只不过因为峰唯一，你可以用nums[mid] < nums[mid+1]判断在上升沿还是下降沿，收缩逻辑和 162 几乎一致。

第二类是寻找旋转排序数组的最小值，比如 LeetCode 153。数组由有序数组旋转而来，值的关系有一个断点。这里的二分依据是比较nums[mid]和nums[right]，判断中点是在断点的左侧还是右侧。它和峰值二分的相似点在于“数组不是完全有序但仍可二分”，但比较对象和收缩规则完全不同，需要注意区分，不能把 162 的模板硬套上去。

第三类是二分答案型题目，也就是热词里常出现的“爱吃香蕉的狒狒”那类题（LeetCode 875）。这类题是对“答案”进行二分，而不是对数组下标二分，每一轮用check(mid)判断当前速度是否可行。check函数写得好不好直接决定成败。这和 162 的“对下标二分”又是一层不同的思路。

5.3 为什么不用三分查找

有人可能会想，既然要找峰顶，那用三分查找每次把区间分成三份，比较两个中点的值，是不是更快？

理论上看，三分查找确实常用在“单峰函数求极值”的场景，比如山脉数组。但 162 并不是单峰数组，它可能有很多峰。三分法在每一步都要比较两个位置mid1和mid2，然后根据两者的高度关系判断丢弃哪一段。如果区间内存在多个峰，三分法可能会因为两个中间点都落在同一侧斜坡上而做出错误判断，丢掉包含峰顶的区间。

更重要的是，162 的二分只需要 O(log n) 次比较，已经达到理论下限。三分每次保留 2/3 区间，虽然也是对数级，但常数更大，而且前提条件更苛刻。所以直接用二分是最稳的解法，不要为了炫技而用三分，反而把自己绕进去。

6. 实测中的坑与排查笔记：我踩过的四个陷阱

6.1 陷阱一：不由自主地想先排序

这道题最大的坑，或者说最隐蔽的坑，其实是思维惯性。我一开始写代码的时候，第一反应是想调用sort()把数组排个序，然后找最大值。幸好写用例的时候及时发现：排序会彻底改变元素的位置关系，返回的下标就不再是原数组中的峰值下标了。

这个错误想法在评论区相当常见。要知道题目要的是“原数组中的峰值的下标”，排序后一切索引都失去了意义。遇到无序数组的二分题，先冷静几秒钟，确认题目到底在找“值”还是在找“位置”。找值可能需要排序，找位置则往往需要保留原始顺序。

6.2 陷阱二：while (left <= right) 的越界与死循环

我在第一次按照普通二分的习惯写while (left <= right)时，直接就报错了。原因是当left == right时，mid = left，此时访问nums[mid + 1]，如果mid正好是最后一个元素，就会数组越界。即便没有越界，这个循环也可能在收缩过程中出现left和right交叉但答案丢失的情况。

解决方案就是一开始就用left < right的模板。如果你非要用left <= right，那么必须额外判断mid == right的情况，代码会多出好几个分支，容易出错。实测下来left < right配合right = mid的模板最顺手，建议直接把这个模板背下来。

6.3 陷阱三：用 nums[mid] > nums[mid-1] 的边界爆炸

还有一种常见写法是换成nums[mid] > nums[mid - 1]作为判断条件，同时尝试用三分或递归实现。这样做不是不行，但必须非常小心mid = 0的情况。在left < right的循环中，mid是可以取到 0 的（比如数组只有两个元素时），此时访问nums[mid - 1]直接就崩溃了。

如果你特别喜欢这种写法，就必须把循环改成while (left < right)且把mid计算改成mid = left + (right - left + 1) // 2这种向上取整的写法，逻辑会绕不少。我的建议是：不需要给自己加难度。nums[mid]和nums[mid+1]这一对比较是天然安全的，用它们就好。

6.4 面试延伸：考官想听你说什么

如果把 162 作为面试题，简单说对代码是不够的，面试官通常会追问三个问题：

第一，为什么用二分？你要回答因为峰值是局部性质，只需局部信息就能排除一半区间，复杂度 O(log n) 优于 O(n) 遍历。

第二，为什么峰值一定存在？你要回答边界外是负无穷，上升趋势不可能无限持续，所以至少有一个转折点。

第三，循环结束时为什么left就是答案？你要回答循环不变量：区间始终包含至少一个峰，区间长度为 1 时该点必然是峰。

把这三个问题回答顺了，这道题才算真正吃透。比死记硬背代码重要得多。

本来想再写一道类似的题做对比，但篇幅已经足够长。个人体会是，二分查找从来不应该是“有序数组的专属工具”，它的本质是“在每一步都能利用既有信息排除一半选项”。162 这道题最大的价值，就是把我们从“二分必须有序”的思维定式里拽了出来。如果你最近正在刷二分专题，建议在 162 之后紧接着做 852、153 还有那道二分答案的 875，把这几种二分的变体都过一遍。等到你能清晰说出每一道题“比较的是什么、收缩的依据是什么、循环不变量是什么”，二分这个专题基本就稳了。我自己是在把这几题串起来做完之后，才对“二分”这件事有了真正的手感。