前阵子复盘二分法系列题目LeetCode 162《寻找峰值》让我印象最深。第一眼看到这道题我相信多数人的反应和我一样数组元素不是有序的凭什么用二分法要判断nums[i]是不是峰值不是得同时比较左右两个邻居吗可题目偏偏要求在 O(log n) 时间内完成。当时我把这道题归到“二分法看起来能用但其实不能用”的类别里结果把原理想透之后才发现二分法从来不是有序数组的专利只要搜索区间能按确定性规则丢掉一半二分就能成立。这篇文章不打算摆一段代码就完事而是把寻找峰值里最容易忽略的原理、边界处理、面试时怎么把正确性讲清楚一次性聊透。适合正在刷二分专题、准备算法面试或者工作中想用更高效方式找趋势转折点的读者。1. 从数组无序怎么能二分这个困惑说起1.1 峰值问题的准确定义寻找峰值这道题描述起来很简洁给你一个整数数组nums找到任意一个峰值元素并返回其索引。峰值元素是严格大于左右相邻值的元素。数组的边界有个特殊约定你可以假设nums[-1] nums[n] -∞也就是说数组最左边元素的“左侧”和最右边元素的“右侧”都被看成负无穷。这个负无穷的约定很关键。它把端点也纳入统一的峰值判断逻辑里对于一个端点元素它只需要比唯一存在的那个邻居大就算峰值。比如[1, 2, 1]里索引 1 显然是峰而[3, 2, 1]里索引 0 也是峰因为左侧是负无穷右侧 2 比 3 小。如果没有这条约定你写代码时就不得不在循环外单独判断端点麻烦不说还容易漏。题目要求返回“任意一个”峰值索引。什么叫任意一个假设数组是[1, 2, 1, 3, 5, 6, 4]索引 1值 2是峰索引 5值 6也是峰算法返回哪一个都算对。这一点看起来无关紧要实际上正是二分法能成功的前提之一。如果你画蛇添足非要找到“全局最高峰”那问题性质就变了复杂度也得退回 O(n)。1.2 二分法的本质不是有序而是可判定方向很多初学者把二分法和“数组有序”绑定在一起这是理解上最大的障碍。传统有序数组二分确实依赖单调性中间元素和 target 比较后能确定 target 在左半边还是右半边于是每次丢弃一半。但仔细想想二分法真正需要的是每一次比较都能给出一个确定性的搜索方向。峰值问题里的数组整体无序但局部信息是可判定的只要看nums[mid]和nums[mid 1]的大小关系就能知道峰值更可能藏在哪半边。这就像你在一片完全陌生的山脉里找山顶不需要地图也不需要知道整片山脉的走势只需要看脚下的路是向上还是向下。如果前面是上坡顺着坡走一定能遇到某个山顶如果前面是下坡掉头向上也一定能遇到山顶。每一步都只依赖眼前这两个点的相对高低却足以把搜索范围缩小一半。这种“非有序数组上的确定性收敛”正是二分法家族里容易被忽视的分支。同类的题目还有“二分法求平方根”“旋转排序数组找最小值”。二分法求平方根利用的是单调函数上 target 与 mid 平方之间的大小关系峰值问题利用的则是相邻元素之间的局部方向。两者骨架一致区别只在于“用什么判断丢掉哪一半”。2. 核心原理局部单调性如何锁定峰值方向2.1 哪里有上坡哪里必有峰峰值二分的核心结论可以浓缩成一句口诀比较nums[mid]和nums[mid 1]往数值更大的方向走该方向必定存在峰值。为什么这个结论成立我用生活化的方式解释一下。假设你站在mid这个位置看到mid 1比mid高那么从mid 1开始向右的地形不管中间怎么起伏一定会出现至少一个点它比左右两边都高。原因是数组右侧尽头是负无穷你不可能一路保持上升永远不回头。上升趋势一旦被打破那个“打破”的点就是峰值就算一路升到最右端最后一个元素右侧也是负无穷它本身就是一个峰值。所以峰值一定落在你决定保留的那一侧。反过来也一样。如果nums[mid] nums[mid 1]说明从mid到mid 1是下坡掉头往左走左侧必定存在峰值。注意这种情况下不能把mid丢掉因为mid本身可能正好是那条“下坡”的起点很可能就是一个峰值。这个结论还有个隐蔽的好处它每次只比较一对相邻元素不需要同时看nums[mid - 1]和nums[mid 1]。很多人在这个题上绕远路就是因为他们觉得峰值必须“同时大于左右两边”非要写nums[mid] nums[mid - 1] nums[mid] nums[mid 1]才放心。这样写不仅要多处理mid 0和mid n - 1的边界还容易把思路带偏。事实上你只需要知道“哪边是上坡”剩下的交给“上坡必有峰”这个定理就行。我之前画过几个数组形态来验证自己的理解你也可以在纸上画一画单调递增[1, 2, 3, 4, 5]任意位置看右边都是上坡峰值在最右端索引 4单调递减[5, 4, 3, 2, 1]任意位置看右边都是下坡峰值在最左端索引 0多峰形态[1, 3, 2, 4, 1]索引 1 和索引 3 都是峰分别对应左右两个山包。这个规律对纯单调数组也成立验证起来非常快。2.2 为什么可以放心丢掉一半理解“上坡必有峰”只是第一步还需要确认一件事情丢掉另一半时会不会把唯一的峰丢出去答案是不会因为我们保留了“包含某个峰值”的那半边。更精确地说算法维护的是一个候选区间[l, r]这个区间在每一轮迭代里都至少包含一个峰值。初始时整个数组一定至少有一个峰值候选区间是完整的。每一轮比较之后被丢掉的那一侧要么根本没有峰值要么只丢掉了一些“非目标的峰值”而保留侧仍然至少存在一个峰值。等到l r时区间缩小到单点这个点就是合法峰值。这也是面试时回答“为什么你的二分是对的”最核心的论点不是“二分找到了唯一峰”而是“候选区间自始至终没有丢失全部峰值”。2.3 多峰场景下方向选择的自由度有的读者会问如果数组里有很多峰我每次都朝数值更大的方向走会不会只找到其中一个固定的峰没错确实是这样。但题目要求返回“任意一个”所以这种偏向性是允许的甚至可以说正是因为只要求任意峰才给了二分法发挥的空间。我自己调试时习惯拿一个多峰数组走一遍比如[1, 3, 2, 1, 5, 6, 4]。第一次mid 3nums[3] 1小于nums[4] 5于是丢弃左半边最终走向右侧的峰。如果换一个起始长度或者换一个mid位置也许它会走向左侧的峰。不管最终落在哪返回值一定满足峰值定义。这个“不确定性”不是算法的缺陷而是题目给的自由度。3. 二分实现逐步拆解每一行代码在干什么3.1 标准的 Python 与 Java 实现先给代码这段代码是最简洁也最不容易出错的版本。def find_peak_element(nums): 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 leftclass 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; } }我实际面试时还见过有人用 Go 写逻辑完全一样只是语言语法差异。这版实现的核心思路是循环持续到左右指针相遇退出时left就是一个峰值索引。3.2 三个关键细节为什么这样收缩边界这段代码里有几个细节刚接触时最容易写错我逐个拆开讲。第一个细节为什么nums[mid] nums[mid 1]时执行left mid 1而不是left mid因为此时已经确定mid不可能是峰值——它的右边邻居比它大它至多是一个“上坡路上的点”。峰值只能出现在mid 1及其右侧所以left可以直接跳到mid 1把mid排掉。这一步不会漏答案因为右侧区间仍然有峰。第二个细节为什么nums[mid] nums[mid 1]时执行right mid而不是right mid - 1因为当右边比左边低时mid本身可能就是峰值。比如单调递减数组[5, 4, 3, 2, 1]中mid 2时右边是 2比 3 小但真正峰值在索引 0并不在mid 2处。可你不能因此把mid排除因为如果是[5, 4, 3]这种短数组mid 1nums[1] 4比nums[2] 3大峰值却可以是索引 0也可能是索引 1 的右边不对索引 1 左边 5 大于 4所以它不是峰索引 0 才是峰。这种情况下mid确实不是峰但我们不知道所以保守地保留mid是安全的。right mid让mid仍然留在候选区间内不会漏。第三个细节为什么mid 1一定不会越界因为循环条件是left right所以当left right时mid最大也只能是right - 1想象left right - 1的场景mid 1最大正好是right不会访问到数组外面。这一点很关键如果你写成while left right在left right时算midmid就等于right再去访问nums[mid 1]就越界了。另外还有一个习惯问题mid (left right) // 2在left right很大时可能整数溢出虽然这道题一般不会但统一写成mid left (right - left) // 2是更稳妥的做法。3.3 完整走一遍用两个数组验证指针移动我拿一个数组[1, 2, 3, 1]手动推演一遍。初始left 0, right 3mid 1nums[1] 2 nums[2] 3说明右侧有上坡执行left 2此时left 2, right 3mid 2nums[2] 3 nums[3] 1说明右边是下坡执行right 2循环结束返回left 2。索引 2 的值是 3确实大于左右邻居是峰值。再换一个数组[1, 3, 2, 1]初始left 0, right 3mid 1nums[1] 3 nums[2] 2执行right 1left 0, right 1mid 0nums[0] 1 nums[1] 3执行left 1返回left 1索引 1 的值 3 是峰值。两个例子一个往右追、一个往左追但最终都停在合法峰值上。我在本地调试时喜欢在循环里打印left、right、mid三个值确认区间确实在快速收敛而不是左右指针原地打转。4. 边界条件与评测机制那些让你WA的细节4.1 数组长度为 1 的特殊场景代码写出来只有短短几行但边界情况才是真正拉开差距的地方。首先是最简单的数组只有一个元素。比如nums [7]按照题目对边界外负无穷的约定它本身就是峰值。上面的代码里while left right根本不进入循环直接返回left 0正确。有些同学会把这道题写成“先判断长度是否为 1再二分”其实完全没必要。这个天然的处理方式也是我喜欢left right模板的原因之一它把长度 1 直接覆盖了不需要额外分支。4.2 单调递增和单调递减峰值在端点的验证端点峰值是很多人的盲区。看单调递增数组[1, 2, 3, 4, 5]mid 2nums[2] 3 nums[3] 4left 3mid 3nums[3] 4 nums[4] 5left 4返回 4端点峰值正确。单调递减数组[5, 4, 3, 2, 1]mid 2nums[2] 3 nums[3] 2不成立right 2mid 1nums[1] 4 nums[2] 3不成立right 1mid 0nums[0] 5 nums[1] 4不成立right 0返回 0同样正确。这两类数组恰好是最容易让人怀疑二分正确性的案例因为峰值在边界上而二分直觉上总是往中间走。跑通这两个极端之后我心里就踏实多了。4.3 相邻元素相等时怎么办这是评论区讨论最多的问题之一。如果数组里出现相邻元素相等比如[1, 2, 2, 1]按严格大于的定义没有任何位置是峰值。但上面的二分不会报错它会返回某个索引比如中间那个 2。这时候返回值严格来说并不“合法”。所以这里需要明确一个前提LeetCode 原题在绝大多数版本里都保证相邻元素不相等或者测试数据本身避开了完全相等的相邻情况。我在面试中遇到这道题时会主动跟面试官确认一句“题目保证相邻元素不相等吗”如果面试官说相等那就要重新讨论峰值定义通常的做法是放宽为“大于等于”也算峰值或者用线性扫描处理重复段。刷题平台上的提交以平台数据为准但原理上要知道这个坑的存在。4.4 常见错误写法对照我把踩过的坑和容易犯的错整理成一张表方便自己以后复习也给读者一个直观对照错误写法问题后果正确做法while (left right)循环内直接比较nums[mid]与nums[mid 1]left right时mid 1越界或返回结果不稳定用while (left right)保证比较时区间至少有两个元素right mid - 1在单调递减数组中漏掉左端峰可能访问负数索引峰值可能就在mid收缩时保留它写成right mid同时比较nums[mid - 1]和nums[mid 1]再决定方向边界处理复杂mid 0时访问nums[-1]出错只比较nums[mid]和nums[mid 1]方向已经足够想在二分循环里额外记录“当前最大值”把问题变成找全局最大值复杂度升到 O(n)失去二分意义只维护候选区间别的什么都不用记mid (left right) // 2left right可能溢出虽然此题概率低但坏习惯写成mid left (right - left) // 2第五个错误我见过不少——有些人写着写着觉得“反正要找峰不如顺便比一下谁最大”。一旦你这么想代码就会不自觉引入 O(n) 遍历二分名存实亡。这道题必须时刻记住我们只需要任意峰不是最高峰。5. 复杂度分析与正确性证明给面试官看的版本5.1 时间复杂度是怎么算出来的时间复杂度 O(log n) 的推导很直接。每轮循环候选区间[left, right]的长度至少缩小一半。初始长度为n经过k轮之后长度不超过n / 2^k当n / 2^k 1时循环结束所以k不超过log2(n)。空间上只用了left、right、mid三个整型变量是 O(1)。这个推导在面试时最好用一句完整的话说出来“每次循环都把搜索范围缩小到原来的一半所以是 O(log n)空间 O(1)。”千万不要只报一个结果让面试官觉得你是背的。5.2 正确性的三句话证明我刷完这道题之后总结了一套面试时能讲清楚、又不显得啰嗦的证明框架三句话搞定第一句初始候选区间是整个数组而整个数组一定存在至少一个峰值因为数组边界外是负无穷地形不可能无限上升下去。第二句每次比较nums[mid]和nums[mid 1]后如果右边更大从mid 1向右一定能找到峰值如果右边更小[left, mid]区间内一定能找到峰值。因此被保留的区间始终包含至少一个峰值。第三句当left right时区间缩成一个点这个点就是峰值返回它即可。这三句话本质上是“循环不变量 收敛性”的通俗版。面试官如果继续追问“为什么右边更大就一定有峰”就把前面说的反证法讲一遍假设右边没有峰那么从mid 1到数组末尾必须严格递增可最右端外是负无穷最后一个元素天然满足峰值条件矛盾。这个补充能体现出你真的理解而不是光会背模板。5.3 被人质疑只比较一侧会不会丢答案时的回应面试高频追问还有一个你只比较了nums[mid]和nums[mid 1]为什么不看nums[mid - 1]万一峰值正好在mid左边却被你跳过了呢我的回答套路是如果nums[mid] nums[mid 1]说明右边存在必赢的上坡这时我不需要关心左边如果nums[mid] nums[mid 1]说明mid可能是个峰即使它不是左侧也必然有峰。无论哪种情况都存在一个峰值保留在候选区间里。题目只要任意一个峰所以单侧比较的信息量已经足够。再加上峰值定义不需要“全局最高”所以不存在“丢掉唯一最大峰”的顾虑。6. 变形与实战延伸峰值问题不止一道题6.1 对称问题找局部最小值理解了峰值二分的本质找局部最小值几乎是白送的。把边界约定改成nums[-1] nums[n] ∞然后把比较方向反过来就行。def find_local_min(nums): 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这里的思想和峰值完全对称nums[mid] nums[mid 1]说明右边是下坡往下坡走必有谷否则保留左侧。我第一次看到这题时下意识想重新推一遍定理后来发现只要把口诀改成“哪里有下坡哪里必有谷”代码改一个大于号就行。这种对称性也是二分法魅力的一部分。6.2 二维矩阵找峰值的进阶思路如果觉得一维不过瘾可以去看看二维版本的峰值题比如矩阵中找任意峰值元素。主流思路是“中间列 列最大值”取当前列范围中间的那一列在该列里找到最大值所在的行row然后看matrix[row][mid_col]和左右邻居的大小关系。如果它比左右邻居都大它自己就是二维峰值否则就往数值更大的那一边收缩列范围。这个方案的复杂度是 O(m log n)因为每一轮需要在中间列上扫描一次找最大值扫描代价是 O(m)列二分是 O(log n)。更进阶的 O(m n) 爬山法也能做但代码量和边界复杂度都会上升。我的建议是先把一维的“上坡必有峰”真正吃透二维只是同样的思想多加了一个维度方向判断从“左右”变成“上下左右”而已。6.3 从刷题走向业务二分思想的现实落点最后说点题外话。这类“找转折点”的问题在真实业务里其实很常见。比如分析某段时间的用户访问量曲线想找到流量尖峰对应的时间点或者看服务器负载曲线想知道一天中压力最大的时刻又或者在传感器时间序列里找异常极值。现实数据往往有噪声直接套峰值二分会被毛刺干扰通常需要先做平滑、下采样等预处理但核心分析思路里“比较相邻两点、判断方向、缩小范围”仍然是好用的抓手。回到算法本身二分法、寻找峰值、二分法查找、二分法求平方根代码这些关键词之所以经常一起出现就是因为它们共享同一套“区间收缩”的底层逻辑。区别只在于判断方向的依据是什么求平方根依据的是mid * mid和target的大小找峰值依据的是相邻元素的高低找旋转数组最小值依据的是中点和右端点的相对关系。把“方向可判定”这个抽象概念建立起来你就不会再问“无序数组怎么能二分”这种问题了。个人经验是刷二分题别急着背模板先问自己三个问题候选区间是什么每轮通过什么信息判断丢弃哪一半区间收缩到什么时候停止想清楚这三个问题不管题目怎么包装你都能快速写出正确的二分。