我想从一个面试场景说起。面试官递过一个数组[4,5,6,7,0,1,2]问我“这个数组是乱序的还能用二分查找吗”。我当时脑子里全是“二分的前提是有序数组”差点直接答“不能”。可自己笔画了两下就发现这数组虽然整体无序但它是两段递增序列拼起来的最小值恰好卡在拼接处用二分完全能找出来。后来我才明白一个关键道理二分查找真正依赖的从来不是单调性而是序列具备某种“二段性”。这也是这篇文章想讲清楚的东西——什么是二段性怎么用二段性在非单调序列上寻找极值以及我在实际调试中踩过的各种边界坑。如果你想进阶二分查找看过很多模板却总在变形题上卡住这篇文章应该能帮你把底层逻辑理顺。1. 有序才能二分真正的前提是“答案可以被某条性质一分为二”1.1 从一次面试翻车说起先回到那个面试场景。当我意识到旋转数组也能二分时第一个反应是去翻各种“二分变种模板”结果越看越乱有找第一个大于 target 的模板有找最后一个小于 target 的模板有左闭右开区间模板还有左闭右闭区间模板……每个模板都配着自己的边界条件背下来不难可一旦题目换了个形状我又开始怀疑“这个能不能二分行不行”。踩的次数多了我开始总结经验我们这些做题的人之所以频繁翻车是因为把“数组有序”当成了二分的充分条件。实际上只要你能找到一个布尔性质让它在序列上“一分为二”——左边全是一种状态右边全是另一种状态——那二分就能工作。这个思想比“有序”二字强大得多它才是我后来解决一堆极值问题的真正钥匙。1.2 二段性的定义给个严谨但不拗口的定义如果一个区间[l, r]存在一个分界点k使得某个布尔性质P在[l, k-1]上恒为某种取值在[k, r]上恒为另一种取值那么这个区间对性质P就具备二段性。听起来有点抽象我拿升序数组举例。数组[1, 3, 5, 7, 9]是单调的定义性质P(i) arr[i] 5那么从左往右取到的布尔序列是F, F, T, T, T。分界点就是第一个满足P的位置也就是数值5所在的下标。你发现没有单调性只是二段性的一个特例一个升序数组天然能产生这种“前假后真”的二段结构。那旋转数组呢[4,5,6,7,0,1,2]以最小值0为分界左侧[4,5,6,7]中每个元素都大于最后一个元素2右侧[0,1,2]中每个元素都小于等于2。所以如果定义性质P(i) arr[i] arr[r]那么从左往右 P 的取值是T, T, T, T, F, F, F——同样是典型的两段结构。序列虽然没有全局单调性但这个布尔性质却已经“一分为二”了。1.3 为什么“找极值”也能套二分再看寻找极值的问题。假设给定一个“山脉数组”[1,3,5,4,2]峰值是5它本身并不满足“大于某个固定值”这类普通性质但它可以换成相邻关系的视角定义P(i) arr[i] arr[i1]意思是“当前位置还在上升段”。在峰值之前这个值恒为True在峰值之后这个值恒为False。于是序列的 P 取值是T, T, F, F分界点就是峰值。所以“找极值”和“找 target”本质上完全一致都是夹逼分界点。区别只在于找 target 时我们比较的是“mid 和某个固定值”而找极值时我们比较的是“mid 和它的邻居”。这个视角切换是我能把这堆题目统一理解的关键后面所有模板都围绕它展开。2. 把二段性翻译成二分查找一套可复用的判断框架2.1 从“找值”模板到“找分界点”模板传统二分模板长这样“mid 大了就往左mid 小了就往右”核心是比较大小。而二段性模板写的不是“大小”而是“性质取真还是取假”。我给你一个可以直接套的框架def binary_search_segment(nums): l, r 0, len(nums) - 1 while l r: mid l (r - l) // 2 if segment_property(nums, mid): # 你自己定义的性质 l mid 1 # 分界点在右侧 else: r mid # 分界点在左侧含mid return l真正需要动脑子的只有一个segment_property。其余部分几乎原封不动。当循环结束时l r这个位置往往就是分界点也就是我们要找的极值所在位置。这套模板我写了不下二十道题每次只需要替换segment_property内部的一两行比较逻辑。2.2 设计“收敛方向”的三步法三步法看着简单但每一步都有讲究定义性质 P这个性质必须和答案的“分界”强绑定。找极值的话性质通常是“mid 位于极值的哪一侧”。旋转数组里用的是“是否大于最后一个元素”山脉数组里用的是“是否处于上升段”。判断 mid 处 P 的取值取值为真时说明当前位置在分界点的这一侧我们判断目标在另一侧取值为假时说明当前位置在另一侧目标可能就在当前位置或其更左的位置。收缩区间每次收缩都必须保证目标点仍然留在新区间里绝不能把它丢出去。我给个实际例子。旋转数组里nums[mid] nums[r]为真说明 mid 落在左边那段递增序列里最小值一定在 mid 的右边所以l mid 1。反之说明 mid 已经落在右边的最小值区域附近最小值在 mid 左侧或就是 mid所以r mid。这样一个循环下来区间始终围着最小值收拢。2.3 河流石块类比为了让自己记忆更牢我喜欢用一个“河流石块”的类比。想象一条河中间立着一块石头河水被石头分成两段一段向左流、一段向右流。你可以在任意位置测试“这里的水朝哪个方向流”然后用二分不断缩小区间最终就能定位到石头所在位置。石头就是分界点极值水流方向就是那条布尔性质。这个类比说明了两个重要前提第一性质必须在分界点的两侧“状态不同”否则没法用第二每次测试必须是便宜的一次比较交互就能得到结果。满足这两点二分的对数时间复杂度才有意义。我每次分析一道新题时都会先问自己这道题的“石头”是什么“水流方向”的性质是什么。想明白这两点模板基本就出来了。3. 旋转数组找最小值、山脉数组找峰值与“答案值域”的二分3.1 旋转有序数组找最小值这是二段性最经典的落地题目。给定一个原本升序的数组把它在某个未知位置旋转比如[4,5,6,7,0,1,2]要求找到最小值。完整代码如下def find_min(nums): l, r 0, len(nums) - 1 while l r: mid l (r - l) // 2 if nums[mid] nums[r]: l mid 1 else: r mid return nums[l]几个关键点值得展开为什么和nums[r]比较而不是nums[0]因为nums[0]在数组没有旋转时就是最小值在旋转后可能反而是右侧序列中偏大的值选择它会干扰判断。以最后一个元素作为锚点可以统一处理“旋转了 0 次”和“旋转了若干次”两种情况。为什么nums[mid] nums[r]时移动l当 mid 位于左段说明右段元素整体比 left-segment 的元素小最小值还没越过 mid只能向右找。循环次数是 O(log n)因为每次区间直接砍半。手动走一遍[4,5,6,7,0,1,2]l0, r6, mid3nums[3]7 nums[6]2所以 l4然后 l4, r6, mid5nums[5]1 nums[6]2为假于是 r5再走一轮 l4, r5, mid4nums[4]0 nums[5]1为假r4循环结束nums[4]0就是答案。整个过程每次只需要一次比较非常干净。3.2 山脉数组找峰值山脉数组是另一种极值问题的标准形态。它先严格递增、再严格递减且相邻元素不相等要求找出峰值所在下标。常见写法def peak_index(arr): l, r 0, len(arr) - 1 while l r: mid l (r - l) // 2 if arr[mid] arr[mid 1]: l mid 1 else: r mid return l这里arr[mid] arr[mid 1]就是在判断“mid 是否还处于上升段”。如果是峰值一定在 mid 的右边所以l mid 1如果不是说明 mid 已经在下降段而峰值要么是 mid 本身要么在 mid 左边所以r mid。注意此处是r mid不是r mid - 1因为arr[mid]完全可能是峰值。拿数组[0, 2, 1, 0]来走一遍l0, r3, mid1arr[1]2 arr[2]1为假所以 r1然后 l0, r1, mid0arr[0]0 arr[1]2为真所以 l1循环结束答案就是下标 1即峰值2。如果遇到这种只靠相邻比较就能解决问题的题它的核心就是“用走势判断方向”。3.3 从“数组上的极值”扩展到“答案值域上的二段性”二段性不只在数组元素上出现还大量出现在“答案值域”上。很多优化类问题比如“最小化最大值”“最大化最小值”判断某个候选答案是否可行时可行性的取值在值域上往往也是True, True, ..., False, False或反过来的二段结构。这时我们对“答案”本身做二分每次用feasible(mid)判断能否满足根据结果决定往哪个方向逼近。这类题的标志是题目要求输出一个整数答案而这个答案的范围通常很大比如0到10^9没法线性枚举。你只需要一个判定函数feasible(x)它告诉你x是否可行然后原封不动套用二分的那个框架只是把原来的“性质判断”换成了“可行性判断”。所以二段性的真正威力在于它让你从“容器有序”的思维里跳出来转向“答案可行域分段”的思维。一旦建立这个视角很多看着不需要二分的题最后都能用二分解掉。4. 边界与死循环我用二段性二分时踩过的坑4.1 mid 取整方向决定是否死循环二段性二分最容易翻车的地方不是性质选错而是 mid 的取整方向。很多新手写完之后发现“程序卡死了”十有八九是下面这种写法l, r 0, 1 mid (0 1) // 2 # 结果是0 # 如果某个条件成立执行 l mid此时 l 仍然是0 # 下一次循环 l0, r1, mid0永远重复为什么会这样因为mid (l r) // 2是向下取整。当区间只剩两个元素时mid 会停在左边界。如果这时你写的是l mid那 l 根本不会前进死循环随之而来。解决办法有两个要么把更新写成l mid 1这样即使 mid 停在下边界也不会卡住要么把取整方式改成向上取整mid (l r 1) // 2这样 mid 会停在上边界配合l mid就不会死循环。这两种方案只能二选一混用必出问题。4.2 while l r 结束时l 就是答案而非“答案旁边”另一个常见误解是循环结束后还担心l不是答案非要去检查l-1或l1。我一开始也这样结果多做几步检查反而把边界算错。在“找分界点”这个模板里循环不变量保证了区间[l, r]始终包含目标分界点而while l r结束时l r意味着这个位置就是分界点本身。用前面的旋转数组代码来看循环结束后直接返回nums[l]就是最小值山脉数组直接返回l就是峰值下标。不需要再判断l和l1谁更大。如果你觉得不放心可以在考试或面试现场用两个元素的极简数组手动模拟一遍大多数情况下一轮就收缩掉了。为了便于记忆和排查我列一个常用模板对照表场景mid 取整更新写法结束含义找第一个满足性质的位置向下取整True 时rmidFalse 时lmid1l 即答案找极值趋势判断向下取整True 时lmid1False 时rmidl 即峰值位置需要配合lmid向上取整True 时lmidFalse 时rmid-1l 即答案4.3 重复值、退化场景和复杂度的变化二段性二分并非万能遇到重复值或退化数据时要特别小心旋转数组有重复元素[1,1,1,1,1,0,1]这类输入中nums[mid] nums[r]时我们没法判断 mid 到底在哪一段只能保守地r - 1。这样做保证了正确性但最坏情况下每次只缩一个位置复杂度退化到 O(n)不再是严格的 O(log n)。山脉数组相邻元素相等比如[1,2,2,1]arr[mid] arr[mid1]的判断会变得不可靠二段性被破坏。这种情况下老老实实用线性扫描找峰值别硬套二分。数组长度为 0 或 1写函数前先判空长度为 1 时直接返回下标 0。不要指望二分模板自己处理这种极端输入。真实场景中重复值问题非常常见。我建议把“无重复”和“有重复”两段模板分开背前者是严格 O(log n)后者是退化版都需要知道为什么能跑对。4.4 调试与验证暴力解是二分最好的磨刀石最后分享一个我调试二分题目的固定做法写一个暴力解法作为对照。比如旋转数组最小值题我先写一个min(nums)的线性解法再随机生成长度 1 到 20、元素随机的数组把随机数组喂给二分函数和暴力函数对比结果。跑几千几万次只要有一次不一致立刻就能复现并定位问题。这个方法听起来朴素但特别有效。因为二分的错误往往只出现在极小边界或特定数组形状上光靠肉眼很难看出来。用随机数据暴力对拍能非常快地暴露“收敛方向判断错误”或“越界访问”这类问题。你甚至可以写一个小脚本import random def brute(nums): return min(nums) for _ in range(10000): n random.randint(1, 20) base sorted(random.sample(range(0, 50), n)) k random.randint(0, n - 1) arr base[k:] base[:k] if find_min(arr) ! brute(arr): print(error at:, arr) break跑一轮下来如果全程没报错你对自己的二分实现才真正有了信心。我个人的体会是一个人把二段性二分用得熟不熟并不只看他能不能写出标准模板而是看他能不能快速给任意题目定义一个“会翻转的性质”。一旦你习惯用“分界点”的视角看问题很多原本看起来毫无规律可言的序列都会被慢慢夹逼出来。这个过程没有太多捷径多画图、多写暴力对拍手感自然就出来了。