刷题刷到二分法这个章节很多人的感受是最基础的模板背得滚瓜烂熟一遇到变体就崩盘。今天闭区间、明天开区间、后天 lower_bound换个马甲就认不出来了。二分法之所以被叫作“笔试老大难”不是因为它本身难而是因为区间开闭、循环条件、取整方向这些细节组合在一起非常容易让人在考场上怀疑人生。这篇文章我打算把二分法一次讲透从最基础的模板开始拆解区间开闭背后的循环不变量再逐步覆盖浮点数二分、答案二分、旋转数组二分这些高频变形。刷题新人可以把它当入门笔记有一定基础的老手可以直接跳到第 3 章和第 5 章那里有我实际踩过的坑和调试经验。1. 二分法到底是什么先搞懂核心逻辑1.1 猜数字游戏和信息论视角二分法对应的生活场景就是小时候玩过的猜数字游戏从 1 到 1000 里随机想一个数字你每猜一次对方告诉你猜大了还是小了用最优策略能在多少次内保证猜中答案是 10 次以内。因为每次猜测都能排除掉一半的可能性1000 缩小到 500、250、125……最多 10 轮就能锁定答案。这个“每次排除一半”的机制就是二分法的灵魂。从信息论角度看一次“大了还是小了”的比较只产生 1 bit 信息而 n 个候选值需要 log2(n) bit 信息才能唯一确定所以比较次数下界就是 log2(n)。二分法恰好能达到这个下界。理解这一点你就明白为什么二分法的时间复杂度是 O(log n)为什么它在百万、一亿级数据里依然能“秒出结果”。很多初学者觉得二分法不过是“在一个有序数组里找数”这个理解太窄了。它本质是一种通用的搜索加速框架只要你能定义出“单调的排除规则”就能用二分把线性搜索变成对数搜索。1.2 适用条件不是所有“数组”都能二分二分法有三个前提值得单独拎出来检查数据支持随机访问。数组可以链表不行因为链表拿中间元素要 O(n) 时间二分就没有意义了。存在一个单调的分界条件。最经典的场景是数组整体有序但严格来说“整体有序”不是必需的。旋转排序数组、局部峰值这类问题也可以二分因为它们满足“分界点两边性质不同”这个条件。目标值可以和中间值进行比较并且比较结果能帮助我们排除一半候选区。很多人在笔试里判断“一道题能不能二分”时只记得第一个条件数组有序。结果遇到旋转数组、找峰值、二分答案这类题就懵了。记住后面两条单调的分界条件和可比较性才是更本质的东西。只要你能写出一个谓词 f(x)使得 f(x) 在左半部分为真、右半部分为假或者反过来那么这道题大概率可以用二分做。1.3 复杂度为什么二分快得离谱我们来算一笔账。假设数据规模是 n1e8一亿线性扫描最坏要执行一亿次比较二分查找只需要约 log2(1e8) ≈ 27 次比较。这个差距是千万级别的。在笔试中如果题目要求整体 O(n log n) 甚至 O(n log² n) 的算法二分往往是其中必不可少的一环。排序本身是 O(n log n)如果你在排序后的数组上进行多次查找每次都线性扫描整体复杂度会变成 O(n²)直接超时。换成二分查找多次查找的总成本也只有 O(n log n)这是性能上的本质差异。不过要提醒一句二分法只是把“比较次数”降到了对数级别前提是每次拿到中间元素的操作成本是 O(1)。如果你拿的是链表或者你的“中间”还需要额外扫描复杂度分析就得重新算。这也是为什么算法题里很少看到“对链表做二分”的解法。2. 笔试中最常见的几种二分模板2.1 模板一左右闭区间 [left, right]这是所有人第一次接触的模板也是最直观的写法def binary_search(nums, target): left, right 0, len(nums) - 1 while left right: mid left (right - left) // 2 if nums[mid] target: return mid elif nums[mid] target: left mid 1 else: right mid - 1 return -1这个模板的关键点有三个。第一mid 用left (right - left) // 2而不是(left right) // 2避免 left right 溢出整型范围。在 Python 里这个问题不明显但在 C、Java 里是经典考点我建议从一开始就养成这个习惯。第二循环条件是left right因为闭区间在 left right 时还有一个元素没有检查加了等号才能保证覆盖。第三每次更新区间时都要把 mid 排除掉即left mid 1或right mid - 1因为 mid 已经比较过了不排除会导致死循环。这个模板适合“查找目标值的精确下标”这类最简单的问题。找不到时返回 -1或者按题目要求返回插入位置。这里顺带提一句如果题目问的是“搜索插入位置”闭区间模板在循环结束后left 正好是目标应该插入的位置但很多人容易记混不如直接用后面要讲的 lower_bound 模板省心得多。2.2 模板二左闭右开 [left, right)左闭右开是工程界很常用的写法很多编程语言标准库里的 lower_bound 系列函数用的就是这种区间定义def binary_search(nums, target): left, right 0, len(nums) while left right: mid left (right - left) // 2 if nums[mid] target: return mid elif nums[mid] target: left mid 1 else: right mid return -1区别在哪里right 初始值是len(nums)而不是len(nums) - 1含义是“右边界不包含在搜索区间内”。这带来两个好处一是当搜索区间缩空时left right 自然指向第一个不小于 target 的位置这个位置恰好是“如果 target 不存在应该插入的位置”免去了闭区间写法里返回 left 还是 left 1 的纠结二是更新 right 时不需要减一直接right mid而 left 仍然要left mid 1因为 left 会被 mid 占据而 right 本身不参与搜索。我自己的经验是一旦你习惯了左闭右开就再也不想回到闭区间了。它尤其适合后面要讲的“查找第一个/最后一个位置”类问题。唯一的代价是初学时理解起来稍微绕一点但只要记住“right 是一个哨兵它不参与搜索”很快就顺了。2.3 模板三寻找第一个大于等于目标值的位置lower_boundlower_bound 是二分法真正的万能钥匙。它的定义是在有序数组中返回第一个不小于 target 的元素下标。如果所有元素都小于 target返回 len(nums)。def lower_bound(nums, target): left, right 0, len(nums) while left right: mid left (right - left) // 2 if nums[mid] target: right mid else: left mid 1 return left这个模板的思想是维护一个区间 [left, right)每次检查中间元素是否满足nums[mid] target。如果满足说明答案可能在中点或中点左边把右边界收回来如果不满足说明答案严格在右半部分推进左边界。整个过程保持一个循环不变量left 左边的元素全部 targetright 右边的元素全部 target。循环结束时 left right两者重合的位置就是分界点。有了 lower_bound很多你以前觉得要单独写逻辑的问题都可以套模板解决。比如“搜索插入位置”直接返回 lower_bound(nums, target) 就是答案。再比如“找到 target 的左边界”也是 lower_bound(nums, target)。这个思路非常重要我会在第 4 章反复用到。2.4 模板四upper_bound 与边界系列的统一写法upper_bound 返回第一个大于 target 的下标def upper_bound(nums, target): left, right 0, len(nums) while left right: mid left (right - left) // 2 if nums[mid] target: right mid else: left mid 1 return left和 lower_bound 相比唯一的区别就是把换成了。就这么一个符号的差别组合起来可以解决“第一个等于 target”“最后一个等于 target”“统计 target 出现次数”等一大类问题需求实现第一个等于 target 的下标lower_bound(nums, target)最后一个等于 target 的下标upper_bound(nums, target) - 1第一个大于 target 的下标upper_bound(nums, target)最后一个小于 target 的下标lower_bound(nums, target) - 1统计 target 的出现次数upper_bound(nums, target) - lower_bound(nums, target)我强烈建议把这两个模板背熟但更重要的是理解为什么它们长这样。其实你可以把 lower_bound / upper_bound 理解成“对谓词条件做二分”lower_bound 的谓词是nums[mid] targetupper_bound 的谓词是nums[mid] target。只要随时能写出谓词任何“边界查找”题你都能现场推出正确写法而不是背一个记一个。这个表格在笔试里非常实用。比如“统计有序数组中某个值出现的次数”这个经典问题直接用它就能 O(log n) 解决而不是先二分找到一个位置再左右扩散——那样最坏会退化成 O(n)数据量大时直接超时。这个坑我在真实笔试里见过很多人踩。3. 为什么会有这么多模板区间开闭的底层逻辑3.1 循环不变量一切边界条件的根源如果你只是背模板那你遇到变体题时大概率会翻车。真正让你稳的是“循环不变量”这个思想。它的意思是在每次循环开始之前你的程序状态都必须满足某个不变的性质你做的每一步操作都必须保证这个性质在下一步循环前依然成立。拿 lower_bound 来举例。我们从左闭右开区间 [left, right) 出发这个区间是“答案可能存在的位置”的集合。同时我们可以维护两个更强的约定[0, left) 区间内的元素都严格小于 target[right, len(nums)) 区间内的元素都大于等于 target答案如果存在就在 [left, right) 里。每次循环我们取中间位置 mid 检查。如果 nums[mid] target说明 mid 及左边的元素都不可能成为“第一个大于等于 target”的位置我们把 left 推进到 mid 1这样 [0, left) 依然全部小于 target不变量保持。如果 nums[mid] target说明 mid 及右边的元素都满足条件我们把 right 收回到 mid这样 [right, len(nums)) 依然全部大于等于 target不变量也保持。循环结束时 left right此时 [0, left) 全部小于 target[left, len(nums)) 全部大于等于 targetleft 就是我们要找的答案。这个“保持不变量”的思维比死记 left 1 / right - 1 要可靠得多。因为当你面对一道新题只要定义了不变量循环怎么写、边界怎么更新都是推导出来的而不是猜的。这也是为什么有些人刷了很多二分题依然要靠模板硬套而有些人遇到新题也能十分钟内写对——差距就在这里。3.2 循环条件left right 还是 left right这是初学者问得最多的问题。答案其实很简单看你的区间定义。如果你定义的区间是闭区间 [left, right]那么 left right 时区间内还有一个元素必须继续检查所以循环条件是left right。如果你定义的是左闭右开 [left, right)那么 left right 时区间已经为空循环可以直接结束所以条件是left right。用生活类比来理解。闭区间就像“门牌号从 1 号到 10 号都在范围内”当 left 和 right 都指向 10 号时10 号房还是需要检查的左闭右开就像“门牌号从 1 号到 10 号但 10 号不参与”当 left right 10 时范围内已经没有房子了。很多人会把left right和left right当成两种模板的死记硬背点其实只要先在注释里写下区间定义循环条件一眼就能确定。我写二分题时第一件事永远是写上# [left, right)或者# [left, right]然后才写循环。这个习惯帮我避开了大量低级错误。笔试的时候时间紧张人的第一反应是赶紧写代码但多花 10 秒钟写注释定义区间后面能少调 10 分钟 bug。3.3 mid 的取整方向与死循环如果 mid 的取整方向不对就会写出死循环。举一个最典型的反面例子# 错误示范死循环 def lower_bound_bad(nums, target): left, right 0, len(nums) while left right: mid (left right) // 2 if nums[mid] target: left mid # 错误left 没有前进 else: right mid当 nums [1, 3, 5, 7]target 5 时程序可能陷入 left2, right3, mid2 的循环中。原因是 mid 向下取整恰好等于 left如果更新时又写成left mid区间根本不会缩小。这个问题的本质是在区间只剩两个候选元素时向下取整得到的 mid 会落在两个候选中的左一个如果此时答案是右一个你又把左边界更新成 mid也就是左一个那左边界根本没动死循环就此产生。解决办法有两个方向更新 left 时保证至少前进一位也就是用left mid 1这正是标准模板的做法如果某些问题必须保留 mid 作为左边界比如浮点数二分那就改用向上取整mid (left right 1) // 2。理解了这一点你就明白为什么这个坑在所有模板里都出现不是要你背“取整方向取决于 left 还是 left 1”而是要你确认“每次循环区间长度必须严格减少”。这是二分法避免死循环的唯一硬性要求。4. 二分法的高阶变形从查找扩展到求解4.1 浮点数二分求平方根与方程解当“搜索空间”是连续区间时二分法依然成立只是终止条件从“区间为空”变成“区间足够小”。最常见的例子是求平方根给定一个非负整数 x求其平方根的浮点近似值。def sqrt_float(x): left, right 0.0, float(x) # 固定迭代次数最常见100 次足够达到极高精度 for _ in range(100): mid left (right - left) / 2 if mid * mid x: left mid else: right mid return left写浮点数二分时有几个要点。第一不要用while right - left 1e-7这类精度判断作为唯一终止条件因为当数值很大时浮点数精度可能达不到你想要的差值使用固定迭代次数是最稳妥的每次迭代区间长度减半100 次后的区间长度是原来的 2^-100任何实际问题都足够了。第二比较时通常用 mid 的平方和目标值比较避免直接比较 mid 和真实根因为我们根本不知道真实根。第三注意边界条件x 等于 0 或 1 时要特殊处理否则可能出现 left0, right0 的尴尬。浮点数二分有一个重要提醒它不能直接用while left right做循环条件因为浮点数相等判断和区间为空的概念不同。如果你见到有人写while left right处理浮点二分大概率会有精度相关的 bug。固定迭代次数是最省心的选择代码简单精度还可控。4.2 答案二分把“验证”当单调函数用这是笔试里最常出现、也最容易被忽视的二分应用方式。很多问题看起来不是在“数组里找数”而是“求一个最优值”比如最大值最小化、最小值最大化、在限定时间内完成任务所需的最小速率等。它们的共同特征是你很难直接求解最优值但很容易判断“给定一个候选值 x是否可行”。典型的例子是“D 天内运完货物”一个数组表示每天的货物重量要求在 D 天内按顺序运完问最低的每天运载能力是多少。直接想怎么规划很麻烦但反过来判断就很轻松假设载重能力是 cap然后一天一天地装如果装不下就新开一天最后看用的天数是否不超过 D。并且这个判断随 cap 单调递增——cap 越大用的天数越少或不变。这种情况下二分的是“答案本身”而不是数组下标。写法套路def can_deliver(weights, D, cap): days 1 cur 0 for w in weights: if cur w cap: days 1 cur w else: cur w return days D def min_capacity(weights, D): left, right max(weights), sum(weights) while left right: mid (left right) // 2 if can_deliver(weights, D, mid): right mid else: left mid 1 return left看懂了吗这个题的左右边界不是数组下标而是答案的取值范围can_deliver就是那个“单调的谓词函数”。只要你能写出这样的验证函数并且确认它有单调性原问题就转化成了标准的二分模板。这个方法在笔试里极其高频比如“在 K 小时内吃完香蕉的最小速度”“把数组分成 m 段使每段和的最大值最小”“调度任务求最小最大耗时”等等全是这个套路。关于这个题型我有个特别想说的经验验证函数的单调性是要论证的不是想当然的。比如“载重越大越容易完成”这个直觉是对的但有些题的“可行性”并不单调硬套二分就会出错。拿到题先画一画 check(x) 随 x 变化的趋势确认一定是单调的再动手写二分。这一步看似多余实际上能帮你筛掉很多不适合二分答案的题。4.3 旋转数组看似无序其实存在单调分界旋转排序数组指的是把一个有序数组从某个位置切成两段然后交换位置例如 [3, 4, 5, 1, 2]。这类数组整体不是有序的但它有两个特性可以利用任意取一个位置 mid我们总能判断 mid 落在左半段还是右半段。更关键的是整个数组可以看作两段有序区间拼接而成分界点处的值变化是断裂的。以求旋转数组最小值为例。思路是观察左端元素 nums[0] 和中间元素 nums[mid] 的关系。如果 nums[mid] nums[0]说明 mid 在左半段最小值在 mid 右边因为右半段开始才是最小值所在否则 mid 在右半段最小值在 mid 左边或就是 mid 自己。于是可以不断缩小区间。搜索旋转数组中的目标值也是类似思路先判断 mid 落在哪一段有序区间里再判断 target 是否在这一段内。这类题的共同点是数组整体不是单调的但“有序段”是单调的二分仍然可行因为它满足我们前面说的本质条件——存在一个可以判断的单调分界。我个人的建议是旋转数组题在笔试里出现频率不算特别高但一旦出现基础不牢的人基本必跪。因为它破坏了“有序数组”这个最直观的条件考察的就是你懂不懂二分法的本质。你可以把它当作检验自己是否真正理解二分法的试金石。如果这类题你能顺利写对说明前面的循环不变量和谓词思想你已经掌握得差不多了。4.4 二分的更多组合玩法二分很少单独出现更多时候被当成一个“快速收敛的优化器”嵌入更大的算法流程里。常见的组合有二分答案 贪心验证上文提到的运货题就是代表验证函数内部通常是贪心策略。二分答案 DP 验证比如某些划分问题验证环节需要用 DP 判断是否可行二分的只是阈值。二分 前缀和在带权数组上快速验证一个区间和是否满足条件。二分图最优匹配类问题很多“最小化最大匹配边权”的问题也用二分思想。理解这一点你就明白为什么各大笔试都喜欢考二分——它不是在考“你会不会在一个排序数组里折半查找”而是在考“你会不会把一个决策问题改造成可控的验证问题再用对数级代价快速逼近最优解”。这是算法设计的核心能力也是为什么我建议你不要只背模板而是要理解二分本质的原因。5. 实战要点与调试技巧含避坑经验5.1 笔试现场如何快速选择模板我自己的决策流程分享出来给你参考判断题型先问自己这是“查找确切值”还是“寻找分界点/最优阈值”查找确切值用基础闭区间模板找不到返回 -1 或按题意处理找分界点或阈值定义谓词用左闭右开模板写 lower_bound 风格的方法。定义好谓词在注释里写下“如果我判断的是 f(mid)那么 f 为真/假分别意味着什么”。这一步能避免一大半边界错误。选择合适的区间定义和更新方式确定 left/right 初始值、循环条件、左右边界更新方式。写完后手动跑两个用例一个普通用例一个边界用例比如 target 比所有数都小或都大不要偷懒跳过这一步。这几个步骤看起来繁琐但熟练后 30 秒内就能完成。笔试时的紧张会让思维变慢提前把这套流程固化下来能帮你稳住节奏。很多人在考场上犯的错误不是不会写而是拿到题就急着写代码结果把 lower_bound 和 upper_bound 搞混白白浪费大量调试时间。5.2 常见 Bug 与排查方法速查表我把刷题和笔试中亲自踩过、也看别人踩过的典型 bug 整理成一张表症状原因排查方法程序超时 / 死循环mid 取整方向与边界更新不匹配区间长度未严格缩小打印 left、right、mid 三者的值观察区间是否在某一轮不变返回下标越界left 或 right 可能超出 [0, len(nums)-1]在返回前检查 left 是否越界结合“target 不存在”场景推演返回值差 1区间开闭定义不统一比如前半段用闭区间、后半段用开区间统一在代码第一行写下区间定义并保证所有更新都遵循同一定义重复元素时返回错误位置用找精确值模板处理边界查找匹配到 target 就直接 return改成 lower_bound / upper_bound 模板在边界查找里不要提前 return浮点数精度不足用 while (right - left eps) 但 eps 设置过小或数值范围过大改用固定迭代次数100 次target 不存在时返回异常没有考虑 lower_bound 返回 len(nums) 的情况在用到返回值前先判断下标合法性这几条几乎覆盖了我见过的大多数二分 bug。其中“返回值差 1”是最隐蔽的尤其是找右边界时很多人会混淆left、left - 1、right之间的关系。我的建议是右边界问题一律用upper_bound - 1来求不要自己手推左右边界更新逻辑这个绕法可以当成纪律来执行。5.3 提交前的五组边界测试用例无论你怎么写二分提交之前建议至少要跑下面五组数据空数组或空搜索区间单元素数组target 比数组所有元素都小target 比数组所有元素都大数组里存在多个重复 target。其中最容易出问题的是第 3 组和第 4 组因为很多人的模板在“找不到目标值”时返回的 left 或 right 会越界。针对这两组用例要特别检查返回值是否需要在调用处做合法性判断。重复元素则是边界查找题的主要考点统计出现次数时一定要用upper_bound - lower_bound的方法而不是找到第一个之后左右扩散。左右扩散在极端情况下会退化成 O(n)笔试的数据规模通常会给你一个超时的大惊喜。我通常在本地写一个简单的测试函数把这五组用例一次性跑完再提交。这个习惯大概花不了两分钟但能明显降低在一道看似简单的二分题上翻车的概率。尤其是“空数组”这个用例很多模板在len(nums) 0时返回的 left 是 0看起来没问题但如果你后续用这个下标访问数组就崩了。5.4 笔试现场的时间分配建议二分题如果在笔试中单独出现一般应该控制在 10 到 15 分钟内完成包括写验证函数。如果 20 分钟还没调通最可能是区间定义或者谓词写错了。这时候不要反复改边界而是停下来在草稿纸上画一条数轴把 left、right、mid 的位置和区间包含关系标出来往往一眼就能发现问题。如果实在调不出来先切换到后面的题不要在一道题上死磕。笔试的时间管理比单题的完美主义重要得多。我个人还有个习惯写完二分后会在注释里写一句“区间定义[left, right)”。这样即使一个小时后回来看这段代码也一眼能想起当时的逻辑。这个习惯在我准备笔试期间帮我省下了无数重新阅读理解的时间。代码是写给下一个自己看的边界清晰比少写一行注释重要得多。我自己最开始也是靠背模板入门真正让我不再翻车的是想明白循环不变量以及养成“先定义谓词和区间再写循环”的习惯。每次写二分时多花 30 秒做这一步后面调试时间能省半小时。如果你正在准备笔试不妨把文中的五组边界用例当成固定流程每次写完都跑一遍坚持几周之后你会发现二分题突然变得非常机械甚至有点无聊——那时候你就真的拿下了这个“老大难”。