开头看到“寻找峰值”这道题第一反应大多是这样的数组无序要找峰值先遍历一遍每个位置和左右比一比O(n)搞定收工。然后看到题目要求的时间复杂度是 O(log n)很多人会愣一下——无序数组怎么二分这题是不是出错了没有出错。162这道题是二分查找里非常经典的一道“反直觉”题目它在LeetCode上的地位不亚于“二分查找”本身。很多刷题攻略里把它列为入门进阶的必做题目不是因为代码有多难而是因为“无序数组也能二分”这个认知一旦打通后面做旋转数组、山脉数组、寻找两个有序数组的中位数这类题目思路会顺很多。这道题的核心定义很简单nums[i] 比它左右两个邻居都大就是峰值。题目还特意说了一句边界位置只看一侧nums[-1] 和 nums[n] 都当作负无穷来对待。最终要求返回任意一个峰值下标即可。本文会从峰值定义的直觉讲起一步步推演为什么无序数组可以用二分给出两种常见的二分实现再把边界用例和容易翻车的细节全部拆开讲一遍最后聊聊它的变种题和面试里真正会被追问的点。无论你是刚开始刷题的新手还是准备面试想查漏补缺的老手这篇都能给你一些不一样的视角。1. 为什么无序数组也能二分峰值问题背后的爬坡逻辑1.1 峰值定义拆解从“局部最大”说起先回到最朴素的定义。峰值就是“局部最大”——一个元素比左边大同时比右边大。注意这里的“局部”很关键它不要求这个元素是全局最大只要在它周围那一小片区域里称王就行。这就像一个山脊上的多个山头。整条山脉有最高峰但沿途会有很多小山峰每个小山峰只要比它脚下两侧的地势高就算一个峰。题目要求的是“随便找一个山头”不是“找最高的那座山”。数组末尾那个负无穷的约定也很有意思。它抹平了边界和中间位置的差异让每个位置都能统一地用“比左侧大且比右侧大”来判断。如果数组是 [1, 2, 3]那下标 2 就是峰值因为 nums[2] 3 大于左侧的 2右侧当成负无穷自然成立。这个定义看起来平淡无奇但它是后续所有推理的地基。峰值不是“全局特殊位置”而是“局部特殊位置”正是因为局部才给二分提供了可操作的空间。1.2 O(log n) 是出题人给出的最强提示刷题时候很多人忽略了一个重要信号题目明确要求 O(log n)而数组也不是某种有序结构。在算法题里看到 O(log n) 的要求九成情况就是在告诉你——用二分。但这里的二分和传统二分有个认知冲突。传统二分的前提是数组有序我们可以根据 mid 的值和目标值的大小关系确定目标到底在左半边还是右半边。这个逻辑靠的是“单调性”。现在数组无序你凭什么砍掉一半砍掉的那一半里万一藏着峰值怎么办这就是162这道题的精髓。它用的是一个更弱的条件——不是全局有序而是“任意两个相邻元素不相等”。这个条件足够让我们做出一个关键的局部判断只要看 mid 和 mid1 的大小关系就能决定下一步往哪边走且不会漏掉峰值。1.3 爬坡论证任意起点向上走一定能遇到峰值想理解这个二分为什么成立最直观的模型是“爬山”。你站在数组的任意一个位置往左边看一眼往右边看一眼。如果两边的值都比当前矮那你脚下就是峰值停下来即可。如果有一边更高那你就往高的那边走一步。这里有个看起来平凡但非常重要的结论只要不断往更高的方向走最终一定能到达一个峰值。为什么因为你每一步都在走向一个比当前位置更高的位置而数组是有边界的。在一个有限区间里高度不可能一直增加下去。走到边界的时候边界外侧被定义成负无穷边界本身必然比外侧高所以边界位置也是一个合法的峰值。换句话说从数组的任意起点出发沿着“更高的方向”走最终一定会停在一个峰顶上。这条性质不依赖于数组的整体有序性只依赖于两个事实数组有限且边界外侧是负无穷。二分的逻辑正是基于这个爬坡性质。每次我们看 mid 位置的趋势如果 nums[mid] nums[mid 1]说明在 mid 右侧有一个向上的坡那么沿着这个坡走最终一定能碰到某个峰值所以峰值一定存在于 mid 的右侧区域。反之如果 nums[mid] nums[mid 1]说明 mid 自身或者 mid 的左侧存在峰值保留左半边继续找。这就是整个二分方案的灵魂二分不是靠“哪里有序”而是靠“哪里一定存在峰值”来判断。2. 标准二分推演两个版本的代码与每一步的依据2.1 闭区间写法l0, rn-1nums[mid] 与 nums[mid1] 比较最常见的写法是维护一个闭区间 [l, r]初始 l0rn-1。每次取中点 mid (l r) // 2然后比较 nums[mid] 和 nums[mid 1]。这里有个关键点需要先明确mid 1 会不会越界在 while l r 的循环条件下mid 永远小于 r所以 mid 1 最大也就是 r不会超出数组范围。这是这个写法能成立的前提。比较的结果只有两种情况nums[mid] nums[mid 1]说明右邻居更高右侧存在上坡峰值在 [mid 1, r] 区间内令 l mid 1。nums[mid] nums[mid 1]说明当前位置比右侧高峰值可能在 mid 本身也可能在 mid 左侧令 r mid。注意第二种情况里r mid 而不是 r mid - 1。这是最容易搞错的地方。因为 nums[mid] 本身可能就是峰值如果直接把 mid 排除掉可能会丢答案。保留 mid才能保证算法正确性。循环结束时l r这个位置就是一个峰值下标。这个写法的好处是直观、好记是大多数题解采用的版本。class Solution: def findPeakElement(self, nums: List[int]) - int: left, right 0, len(nums) - 1 while left right: mid (left right) // 2 if nums[mid] nums[mid 1]: left mid 1 else: right mid return leftC版本几乎一模一样class Solution { public: int findPeakElement(vectorint 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; } };两种代码的复杂度都是 O(log n) 时间O(1) 空间。2.2 为什么比较 mid 和 mid1而不是 mid-1 和 mid1很多初学者会想判断峰值不是应该同时和左右两边比较吗为什么二分里只比较 nums[mid] 和 nums[mid 1]这是一个很值得想清楚的问题。如果同时比较 nums[mid - 1] 和 nums[mid 1]会出现几种情况mid 比左边小但比右边大或比左边大但比右边小这时候你很难决定往哪边走。更重要的是比较 mid-1 还要处理 mid0 的边界越界问题代码会变复杂。只比较 nums[mid] 和 nums[mid 1]本质上是把问题简化成一个“方向判断”。我只需要知道右侧是上坡还是下坡。右侧上坡答案一定在右边右侧下坡答案一定在左边包括 mid 自己。这个判断只依赖一个相邻关系既不需要担心边界又能保证区间收缩的正确性。这有点像走迷宫时只判断前方是上坡还是下坡而不需要同时判断左右两个方向。每走一步只需要看一个方向方向对了最终就能走出去。2.3 循环不变量为什么这个二分不会死循环二分最容易出的问题就是死循环尤其是 r mid 这种写法配合 mid (l r) // 2 的向下取整。我们来验证一下。假设某一轮 l 和 r 已经相邻了即 r l 1。这时 mid (l r) // 2 l。如果 nums[l] nums[r]走 left mid 1 l 1 r循环结束。如果 nums[l] nums[r]走 right mid l此时 l r循环结束。两种情况下循环都会终止因为每次迭代区间长度都在减小要么 left 变大要么 right 变小。区间长度从 n 一路缩到 1迭代次数正好是 log2(n) 级别。顺便提一个细节mid 的计算用 mid left (right - left) // 2在 C/Java 里可以防止 left right 整型溢出。虽然 LeetCode 的测试数据不太会触发溢出但面试官有时候会问写成这种形式更稳妥。2.4 从爬坡视角看这个二分为什么不会漏答案我有一次在讨论区看到一个提问“如果 mid 正好在一个低谷两边都是上坡这时候你说右边一定有峰值所以去右边这个结论对吗”这个问题问得很好。低谷位置 nums[mid] nums[mid 1]其实就是说右侧有个向上的趋势。从数学上说从这个位置开始向右只要一路沿着上升方向走一定会遇到一个转折点或走到边界那个点就是峰值。这个结论不依赖于 mid 左边是什么样因为我们已经不看左边了。而如果 nums[mid] nums[mid 1]情况稍微复杂一些mid 自己可能是峰值也可能左侧有峰值但右侧不一定有峰值比如数组右半段一路下降到底。所以这时候必须把 mid 保留在搜索区间里去左边找。这个“保大保左”的策略本质上就是在维护一个不变量峰值始终在 [l, r] 区间内部。这个不变量是整个二分正确性的核心。每次迭代后峰值的候选区间都包含当前的 l 和 r直到区间收敛到单点那个点必然是峰值。3. 边界条件与特殊用例容易翻车的几个角落3.1 长度为 1 的数组这是最极端的边界nums [2]。按照定义左右两侧都是负无穷所以下标 0 本身就是一个峰值。代码里 left0, right0while 循环根本不进入直接返回 0。正确。很多人在这个用例上焦虑觉得是不是应该特判一下。其实不必代码天然处理了这个情况。这也是闭区间写法的好处初始区间就是正确答案时循环不打扰你。3.2 单调递增和单调递减数组单调递增数组比如 [1, 2, 3, 4, 5]峰值在下标 4。代码走的过程是mid2nums[2]3 nums[3]4走右侧mid3nums[3]4 nums[4]5走右侧left 变成 4循环结束返回 4。正确。单调递减数组比如 [5, 4, 3, 2, 1]峰值在下标 0。代码走的过程是mid2nums[2]3 nums[3]2走左侧 r2mid0nums[0]5 nums[1]4走左侧 r0循环结束返回 0。正确。这两个用例测试的是代码对“上坡/下坡”方向的反应是验证二分正确性的基础用例。3.3 nums[mid] 恰好是端点位置当 mid 0 时比较 nums[0] 和 nums[1]。如果 nums[0] nums[1]说明下标 0 本身就是一个峰值左边界视为负无穷走 r 0循环结束。这个逻辑是完备的因为左边界外侧被定义成负无穷不需要真实比较。当 mid r 的情况不会发生因为 mid (l r) // 2 且 l r 时mid 最大只能是 r - 1。这也是为什么能安全比较 nums[mid 1] 的原因。3.4 多个峰值时返回哪一个题目要求“返回任意一个峰值下标即可”这给了算法很大的自由。比如数组 [1, 3, 5, 4, 2, 6, 1]峰值为下标 2值5和下标 5值6。二分可能返回任何一个取决于 mid 的落点。这个特性是很多人忽略的。如果你自己测试时发现返回值不是预期的那个峰值先别急着说代码错了检查一下是否题目允许任意峰值。LeetCode 的判定逻辑是只要返回的下标对应元素确实是峰值就算通过。3.5 相同元素相邻的坑题目明确说了 nums[i] ! nums[i 1]所有相邻元素不相等。这个条件保证了比较 nums[mid] 和 nums[mid 1] 时不会出现相等的情况。如果没有这个约束比如数组 [1, 2, 2, 1]在平地上二分就会彻底失效——因为无法判断该往哪边走。面试时如果能主动说出“这个解法依赖相邻元素不相等的条件”是一个很好的加分点说明你理解了算法成立的前提。3.6 这些边界用例的测试矩阵用例数组期望输出说明单元素[3]0边界的负无穷约定生效单调递增[1, 2, 3]2峰值在右边界单调递减[3, 2, 1]0峰值在左边界多个峰值[1, 3, 5, 4, 2]2返回任意合法峰值先升后降[1, 2, 3, 1]2标准单峰形态对称谷底[5, 4, 3, 4, 5]0 或 4两个峰值都在边界4. 从162到852变种题与二分查找家族图谱4.1 852山脉数组的峰值索引LeetCode 852题山脉数组的峰顶索引和162非常像。山脉数组的定义是前半段严格递增后半段严格递减整个数组只有一个峰值。题目要求找到那个唯一峰值。162和852的区别在于162的数组可能有多个峰值而且没有全局的增减规律852的数组只有一个峰值增减规律全局成立。但两者的二分代码几乎可以一样。852用 num[mid] num[mid 1] 判断是否在爬坡段是就走右侧否则走左侧。这就是162二分逻辑在“全局单峰”情况下的特化。如果先做852再做162会觉得162很顺反过来先做162再做852会觉得852简直太简单了。两者的关系是包含与被包含的关系。4.2 153寻找旋转数组最小值同一个判断逻辑的不同表达再往外扩展一点153题寻找旋转排序数组中的最小值也用二分但判断条件变成了 nums[mid] 和 nums[right] 的大小关系。如果 nums[mid] nums[right]说明最小值在右半边否则在左半边包括 mid。和162对比可以发现这类二分的共同点都是不需要整个数组有序只需要一个局部的“比较规则”能告诉我们答案在哪一侧。162的规则是“右侧上坡就在右边”153的规则是“右端无序的最小值在右边”。这类题目做多了会形成一个印象二分查找的本质不是“有序数组查找”而是“能通过局部信息排除掉一半搜索空间的问题求解”。有序数组只是这个条件的一个特例。4.3 852与162的本质区别全局有序 vs 局部可判断我把两者的区别列个表这样更直观维度162 寻找峰值852 山脉数组峰值峰值数量至少1个可能多个恰好1个数组形态任意无序相邻不等严格递增后严格递减比较对象nums[mid] vs nums[mid1]同样比较 nums[mid] vs nums[mid1]返回要求任意一个峰值唯一峰值难度中等简单代码层面最核心的区别其实是162需要证明“为什么随便往一个上坡方向走就能找到峰值”而852因为这个证明变得显而易见——单峰结构决定了只有一个坡顺着坡走必然到顶。4.4 判定条件的统一视角什么时候能用二分总结一下一个题目能用二分解的核心条件有三个一是存在一个可判断的“方向规则”使得任意位置都能确定答案在左还是右。二是排除掉的那一半区域不可能含有答案或者含有答案但不影响最终结果比如162只要任意峰值。三是搜索区间能不断缩小最终收敛到答案。很多二分题目的难点不在代码而在找到那个“方向规则”。162提供了一个很好的训练素材它让你看到无序数组也能二分只要你能证明“被排除的部分不会影响答案”就行。5. 刷题多年回头看这些细节面试官更在乎5.1 先说边界再写代码是区分新手和老手的标志我见过很多人在白板上写这道题写之前信誓旦旦写完一跑就挂在边界用例上。比较典型的错误是写了 nums[mid - 1] 来判断结果 mid 0 时直接越界或者写了 r mid - 1把峰值可能的位置直接丢掉了。有经验的做法是动笔之前先把几个边界用例在脑子里过一遍——长度1的数组、单调递增、单调递减、多峰值数组。然后明确说明“我用闭区间 [l, r]循环条件是 l rmid 取左中点所以不会越界”。这一句话就能让面试官觉得你这个人是真的理解二分而不是背模板。我自己的习惯是在白板上先写出“循环不变量”那一行注释搜索区间内一定包含至少一个峰值。然后再写代码。这样就算中间写错回头检查也有一个参考基准。5.2 手写二分容易出错的三个点第一个点是 mid 的计算位置。用 (l r) // 2 在绝大多数场景都没问题但在 l r 可能溢出的语言里C、Java应该写成 l (r - l) // 2。面试官喜欢问这个。第二个点是区间收缩逻辑。nums[mid] nums[mid 1] 时为什么是 r mid 而不是 r mid - 1因为 mid 可能就是峰值把它排除掉就错了。这个点是这道题最容易写错的地方没有之一。第三个点是循环条件的等号问题。如果写 while l r配合 r mid 这种更新方式会死循环。因为当 l r 时mid l r如果走 r mid区间不变无限循环。所以这类二分统一用 l r结束条件是 l r答案就是那个位置。5.3 复杂度会不会被追问为什么一定是 O(log n)二分的时间复杂度证明比较直接每一轮迭代搜索区间长度至少减半因为 l mid 1 或 r midmid 是左中点区间长度从 len 减到最多 len/2所以要 log2(n) 轮。空间复杂度是 O(1)因为只用了几个变量。但如果面试官继续追问“为什么能保证减半后还有峰值”这就回到第一部分的爬坡论证了。我建议准备这道题时把这个几何直觉想透因为面试官很喜欢让人“解释一下为什么二分对无序数组有效”。5.4 一个很少人提但面试好用的验证技巧刷完这道题之后我习惯做一件事写一个暴力验证函数随机生成多组数据对比二分结果和暴力结果是否一致。这不是为了提交而是为了给自己建立信心——尤其是当你手写二分的边界条件拿不准时用随机数据暴力验证是验证正确性最快的方式。import random def brute_force(nums): n len(nums) for i in range(n): left_val nums[i - 1] if i 0 else float(-inf) right_val nums[i 1] if i n - 1 else float(-inf) if nums[i] left_val and nums[i] right_val: return i return -1 def verify(): for _ in range(10000): nums [random.randint(1, 50) for _ in range(random.randint(1, 30))] # 保证相邻不等 for i in range(1, len(nums)): if nums[i] nums[i - 1]: nums[i] 1 sol Solution() idx sol.findPeakElement(nums) left_val nums[idx - 1] if idx 0 else float(-inf) right_val nums[idx 1] if idx len(nums) - 1 else float(-inf) assert nums[idx] left_val and nums[idx] right_val, (nums, idx) print(all passed)这个验证脚本看起来不起眼但能发现绝大多数隐藏的边界问题。我建议你也跑一下尤其是把数组长度压到1和2多跑几次。做这道题的实际体会是第一次看题解觉得“不过如此”真正自己写、自己画图、自己推边界之后才发现主要是卡在爬坡直觉没建立起来。“无序数组里的二分”这个认知一旦建立后面再遇到旋转数组、峰值集合、局部极值这类题目思考路径就会清晰非常多。这个爬坡直觉值得花时间真正想通而不是背下代码了事。
