1. 二分算法到底难在哪从一看就会一写就废说起二分算法二分查找算法这门手艺几乎是每个写代码的人都绕不开的一道坎。它的思想说出来两分钟就能讲明白在一个有序序列里每次拿中间的元素跟目标比一下比目标小就往右半边找比目标大就往左半边找一次砍掉一半很快就能定位到答案。听起来简单到不像话可真正落到键盘上十个里有八个会写出死循环、越界、答案偏一位这样那样的毛病。我自己最早刷题那会儿同一个查找第一个大于等于目标值的位置前后写了七八版debug 的时间比理解算法的时间长了十倍不止。这篇内容我想干的事情很明确把二分算法从背模板拉回到讲清楚为什么。我会从二分算法的适用前提讲起把两段性这个比有序更本质的性质掰开揉碎然后给出一套能覆盖绝大多数场景的写法配合逐行注释、循环不变量验证、常见变体的对照表最后把我这些年踩过的坑整理成一份排查清单。无论你是刚开始接触二分查找算法的新手还是写了几年代码但每次遇到边界都要重新推一遍的老手应该都能从这里拿到点实在的东西。需要提前说明的是二分算法有两种完全不同的用法很多人把它们混在一起导致脑子越理越乱。第一种是在数组里找一个值也就是常说的二分查找第二种是在一个答案区间里猜答案再用一个判定函数去验证这个答案行不行也就是所谓的二分答案。这两者的内核都是每次砍掉一半但落地时的写法细节、复杂度分析、思考方式差别很大。前面的章节先讲透第一种把边界问题彻底解决掉后面再用一整章专门讲二分答案这样学习曲线会顺很多。提示如果你现在正处于能看懂别人的二分代码但自己写就出错的阶段建议先跳过所有模板直接从第 2 节的两段性开始读。模板是结果理解两段性才是原因先有原因再有结果记忆才不会崩。2. 用两段性重新理解二分比有序更本质的性质2.1 有序数组只是二分的入场券不是主角大多数人第一次学二分老师都会强调数组必须是有序的。这句话没错但它容易造成一个误导好像二分算法离不开排序。实际上有序只是让比较中间元素这个动作变得有意义的最简单方式二分的真正前提是——你要查找的序列能够被某个条件切成满足和不满足两段并且这两段是连续的。只要满足这个性质序列不一定有序照样能二分。举个生活里的例子。你手里有一堆产品出厂日期是乱的但每个产品都贴了个标签说明是否已经过保质期。标签的排列是前面全是没过期后面全是过期了——中间某个位置开始状态发生了翻转。这时候你想找第一个已过期的产品根本不需要按日期排序直接用二分去比较标签状态就行。你看有序在这里被替换成了状态单调翻转而翻转这个性质才是二分真正依赖的东西。这个认知上的转变非常关键因为它直接把二分算法的适用范围从有序数组查找扩展到了任何具有单调性质的判定问题。后面讲二分答案的时候你会发现整个框架都建立在单调判定之上而不是数组有序之上。所以请先把二分等于有序数组查找这个等式拆掉换成二分等于单调性上的定位。2.2 二分查找的本质就是找分界点再往深挖一层二分查找做的事情其实就是定位一个分界点。假设我们把序列里的每个位置涂成红色或蓝色红色表示不满足条件蓝色表示满足条件并且约定所有红色都在左边、所有蓝色都在右边。那么二分的任务就是找到最后一个红色和第一个蓝色这两条边界的准确位置。这个视角的好处是它把找值这个问题彻底一般化了。查找某个数 target 在不在数组里其实是问第一个大于等于 target 的位置和第一个大于 target 的位置这两个边界在哪如果这两个边界指向的元素等于 target说明存在否则不存在。查找 target 的首次出现位置本质就是求第一个大于等于 target 的位置查找最后一次出现位置本质就是求最后一个小于等于 target 的位置。所有变体归根结底都是边界定位问题只是问的边界不同而已。一旦接受了二分 找边界这个设定很多原本看起来零散的题型就能串成一条线旋转数组找最小值、寻找峰值、找缺失的第一个正数、求平方根、求第 K 小的数全都是在一个具有单调性质的判定上找翻转点。思路统一了写代码时心里就不会慌。2.3 红蓝染色法一个能画在纸上的理解模型我在纸上推导二分的时候一直用一套叫红蓝染色的模型这里分享给你。做法是把序列里所有的位置先按某个判定条件分成两类左边一类叫红色右边一类叫蓝色保证红蓝之间只有一个分界点。变量的含义约定为left 指向红色区域的最后一个位置right 指向蓝色区域的第一个位置。每轮循环中我们取中点 mid如果 mid 处的元素是红色就说明分界点在 mid 右边于是把 left 挪到 mid如果 mid 处是蓝色就说明分界点在 mid 左边于是把 right 挪到 mid。当 left 和 right 相邻即 right left 1时循环结束此时 right 就是第一个蓝色位置left 就是最后一个红色位置。这个模型的妙处在于它把边界该开该闭循环什么时候停答案是 left 还是 right这三个最容易出错的问题全部回答了而且是几何直观式的回答不依赖记忆。我个人的经验是凡是能把红蓝染色画出来的二分题写起来几乎不会错凡是画不出来的说明判定条件还没想清楚这时候硬写代码基本等于赌博。注意红蓝染色法的前提是判定条件具有单调性即红色区域连续、蓝色区域连续。如果你的判定条件在序列里是红蓝交替的那二分不适用得换思路。3. 三种区间写法的模板拆解与逐行注释3.1 闭区间 [left, right] 写法闭区间写法是最符合直觉的一种left 和 right 都指向当前还有可能是答案的位置。循环条件是 left right因为当 left 等于 right 时这个位置还没有被验证过必须再进去查一次。更新时如果 mid 不是答案就把边界挪到 mid 的相邻位置left mid 1 或 right mid - 1因为 mid 已经不可能是答案了再留着它只会造成死循环。// 在升序数组 nums 中查找 target存在返回下标否则返回 -1 int binarySearch(vectorint nums, int target) { int left 0, right nums.size() - 1; // 闭区间 [left, right] while (left right) { // 区间非空时继续 int mid left (right - left) / 2; // 防溢出写法 if (nums[mid] target) return mid; else if (nums[mid] target) left mid 1; // 答案在右半边 else right mid - 1; // 答案在左半边 } return -1; // 区间空了都没找到 }这个写法有几个细节值得单独拎出来说。第一mid left (right - left) / 2而不是(left right) / 2原因是当 left 和 right 都接近 int 上限时两者相加会溢出变成负数进而导致数组越界访问。这个坑在竞赛题里非常致命我至少见过三次因为这个原因导致的段错误。第二left mid 1和right mid - 1中的加一减一不能省因为进入这两个分支的前提是 mid 位置已经比较过且不相等把 mid 继续留在区间里下一次 mid 可能又算到同一个位置造成死循环。第三这个写法返回的是恰好等于 target 的某个位置但不保证是第一个如果有重复元素返回哪一个是不确定的。3.2 左闭右开 [left, right) 写法左闭右开这个区间表示在 C STL 里随处可见std::lower_bound用的就是它。它的语义是left 指向候选区间的第一个位置right 指向候选区间的后一个位置也就是区间右端点取不到。这种写法下right 的初值是 nums.size() 而不是 size() - 1循环条件是 left right循环结束时 left 和 right 相等这个位置就是答案。// 返回第一个大于等于 target 的位置等价于 lower_bound int lowerBound(vectorint nums, int target) { int left 0, right nums.size(); // 左闭右开 [left, right) while (left right) { // 区间非空时继续 int mid left (right - left) / 2; if (nums[mid] target) left mid 1; // mid 在红区答案在右边 else right mid; // mid 在蓝区答案在左边含 mid } return left; // 此时 left right是第一个 target 的位置 }注意这里right mid而不是right mid - 1因为 mid 有可能是答案当 nums[mid] target 时mid 就是蓝区的第一个位置属于候选不能把它排除掉。而left mid 1是因为 nums[mid] target 时mid 确定是红区答案一定在它右边可以直接跳过。这两条更新规则的差异正是左闭右开写法和闭区间写法最大的不同也是新手最容易写混的地方。3.3 开区间 (left, right) 写法开区间写法里left 和 right 都指向不可能是答案的位置真正的候选区间在 (left, right) 之间。这种写法的初值通常是 left -1、right nums.size()循环条件是 left 1 right也就是当区间里至少还有一个元素时才继续。// 返回第一个大于等于 target 的位置开区间写法 int lowerBoundOpen(vectorint nums, int target) { int left -1, right nums.size(); // 开区间 (left, right) while (left 1 right) { // 区间内还有元素 int mid left (right - left) / 2; if (nums[mid] target) left mid; // 红区边界在右边 else right mid; // 蓝区边界在左边含 mid } return right; // 第一个蓝区位置 }开区间写法的最大优势是它和红蓝染色模型完全对齐left 永远是红色right 永远是蓝色每次 mid 染完之后直接赋值给对应的那一侧不需要考虑加一减一逻辑异常干净。很多算法竞赛选手偏好这种写法就是因为这一点。代价是初值要设成 -1 和 size()看起来有点反直觉需要适应一下。我个人在面试白板上写二分的时候几乎都用这个版本因为它最不容易在紧张的时候出错。3.4 三种写法的对照与选择建议三种写法各有拥趸这里用一张表把它们的关键差异梳理清楚方便你按需取用。维度闭区间 [l, r]左闭右开 [l, r)开区间 (l, r)left 初值00-1right 初值n - 1nn循环条件left rightleft rightleft 1 right命中 target 时的处理直接 return mid需单独处理或退化为找边界同左更新 rightmid - 1midmid循环结束后 l 的位置可能越界到 n第一个 target 的位置同左最适合的场景查找固定值是否存在标准库风格接口找边界、红蓝染色我的建议是只精一种其余能看懂即可。把我个人最推荐的开区间写法练到肌肉记忆遇到需要边界的时候直接套遇到只需要查值存在的场景就用闭区间写法简单直接。不要今天学这个模板明天换那个模板那样每个都学不深反而增加出错概率。选择的标准也很简单看你的题目是要判断存在还是定位边界前者闭区间后者开区间。提示不论用哪种写法mid的值一定要在循环体内、使用之前计算。我见过有人把 mid 写在循环外面循环里 mid 永远不变直接死循环这种错误发生后往往要盯半天才发现。4. 二分查找的四个经典变体从查值到查边界4.1 查找第一个等于 target 的位置在有重复元素的数组里找 target 的首次出现位置等价于求第一个大于等于 target 的位置然后判断这个位置的元素是不是真的等于 target。int firstEqual(vectorint nums, int target) { int left -1, right nums.size(); while (left 1 right) { int mid left (right - left) / 2; if (nums[mid] target) left mid; else right mid; } // right 是第一个 target 的位置 if (right nums.size() nums[right] target) return right; return -1; }这里为什么不能用普通的命中就返回因为命中的 mid 可能不是第一个。比如数组是 [1, 2, 2, 2, 3]目标 2第一次 mid 可能落在最右边那个 2 上直接返回就丢了正确答案。正确做法是把等于归入蓝区也就是把条件设为nums[mid] target时走左移否则走右移让右边界不断向左收缩最终收敛到第一个等于 target 的位置。这是所有找第一个类问题的通用套路。4.2 查找最后一个等于 target 的位置对称的找最后一个等于 target 的位置等价于求最后一个小于等于 target 的位置。做法是把等于归入红区。int lastEqual(vectorint nums, int target) { int left -1, right nums.size(); while (left 1 right) { int mid left (right - left) / 2; if (nums[mid] target) left mid; // 注意是 等于时归红区 else right mid; } if (left 0 nums[left] target) return left; return -1; }把这两段代码和 4.1 对照着看你会发现它们唯一的区别就是判定条件从换成了。这就是红蓝染色模型的威力——换一个边界只需要换一个判定符号其余结构完全不动。很多同学写这两个变体时喜欢另起炉灶造轮子结果写出来的代码风格不一致容易在细节上翻车。4.3 查找第一个大于等于 target 的位置lower_bound这个就是前面反复提到的 lower_bound它是所有找第一个问题的基础。在 C 里std::lower_bound(nums.begin(), nums.end(), target)直接就能用在 Python 里bisect.bisect_left(nums, target)是它的等价物。自己手写的话int lowerBound(vectorint nums, int target) { int left -1, right nums.size(); while (left 1 right) { int mid left (right - left) / 2; if (nums[mid] target) left mid; else right mid; } return right; // 可能是 nums.size()表示所有元素都小于 target }用生活化的比喻lower_bound 找的是排队时该插在哪个位置比如一队人按身高从矮到高排好来了一个身高 175 的人lower_bound 告诉你他应该站在编号为几的人前面相同身高的人他站最前面。这个位置可能是 n表示他应该站到队尾所以调用方必须自己判断边界。4.4 查找第一个大于 target 的位置upper_boundupper_bound 和 lower_bound 只差一个等号它找的是第一个严格大于 target 的位置。C 是std::upper_boundPython 是bisect.bisect_right。int upperBound(vectorint nums, int target) { int left -1, right nums.size(); while (left 1 right) { int mid left (right - left) / 2; if (nums[mid] target) left mid; // 时归红区 else right mid; } return right; }这两个函数配合起来能解决大量实际问题。比如统计 target 在有序数组里出现的次数答案就是upperBound(target) - lowerBound(target)又比如删除数组中所有等于 target 的元素直接一次性搬移即可。我自己写区间查询的时候几乎是把这两个函数当作两个基本积木在用需要什么区间语义就现搭。4.5 循环不变量验证模板正确性的唯一标准写到这里我想强调一个比模板更重要的东西——循环不变量。所谓循环不变量就是在循环开始前、每一轮循环后都保持为真的性质。在二分里最核心的不变量是left 位置如果存在永远不满足判定条件right 位置如果存在永远满足判定条件。以 4.3 的代码为例初始时 left -1这是一个虚拟位置我们规定它不满足条件right n也是一个虚拟位置规定它满足条件因为所有元素都小于 target 时n 就是标准的第一个大于等于的空位。循环中left mid只会在 nums[mid] target 时执行保证新的 left 仍不满足right mid只会在 nums[mid] target 时执行保证新的 right 仍满足。循环结束后 left 1 right中间的缝隙就是分界点right 就是答案。这个验证方法看起来有点抽象但它是唯一能让你在脱离记忆的情况下判断代码对不对的手段。我强烈建议你在第一次学二分的时候拿纸笔把 4.3 的代码在数组 [1, 3, 5, 5, 5, 7] 上手动跑一遍每一步都写清楚 left、right、mid 的值和每次染色的情况。跑完这一遍你对二分的理解会有一个质变。这比背十遍模板管用得多。5. 浮点二分与二分答案二分的真正主战场5.1 浮点二分的固定循环次数写法整数二分关注的是边界在哪浮点二分关注的是精度够不够。因为浮点数的精度问题用while (right - left eps)来控制循环容易因为 eps 选得不好而陷入死循环或者精度不足业界更稳的做法是固定循环次数。// 求 x 的平方根精度到小数点后 6 位 double mySqrt(double x) { double left 0, right x; for (int i 0; i 100; i) { // 固定迭代 100 次 double mid (left right) / 2; if (mid * mid x) left mid; else right mid; } return left; }为什么是 100 次因为每次区间长度减半100 次之后区间长度变成原来的 1/2^100这个数值小到远超 double 的精度极限double 大约有 15 到 16 位有效数字可以说区间早就收敛到一个点了。固定次数写法还有一个好处复杂度是恒定 O(100)不会因为初始区间的大小而改变写题的时候心里有底。通常 60 到 100 次都够用我个人习惯写 100 次多几十次迭代的开销可以忽略不计。5.2 二分答案的解题框架二分答案是二分算法里最有魅力的一部分也是很多人卡壳的地方。它的思路是答案是一个数值这个数值有一个取值范围并且存在一个判定函数 check(x)使得当 x 满足某个单调性质时check 的结果是连续的 true 或连续的 false。于是我们不需要精确计算答案只需要二分这个取值范围用 check 去判断中点行不行最终收敛到答案。标准框架长这样// 求满足 check(x) 的最小 xcheck 具有单调性x 越大越容易满足 int solve() { int left 下界 - 1; // 保证不满足 check int right 上界 1; // 保证满足 check while (left 1 right) { int mid left (right - left) / 2; if (check(mid)) right mid; // mid 可行尝试更小 else left mid; // mid 不可行必须更大 } return right; }这套框架看起来和整数二分一模一样核心区别在于 check 函数是需要我们自己写的它决定了答案的单调性怎么构造。这也是二分答案真正的难点——不是二分本身而是证明 check 的单调性并且写对 check。典型的题比如分成 K 段子数组使得最大子段和最小答案的范围是 [数组最大值, 数组总和]check(mid) 判断当每段和不超过 mid 时最少需要分成几段是否不超过 K。随着 mid 增大所需段数减少这就是单调性的来源。5.3 判定函数怎么写得又快又对check 函数是二分答案的命门我总结了几条写它的经验。第一先写暴力版本的 check确保逻辑正确再考虑优化。很多题的 check 直写是 O(n)配合外层 O(log V) 就是 O(n log V)完全够用不要一上手就追求花哨的优化。第二确认单调方向要想清楚x 变大时 check 是更容易满足还是更难满足这决定了你该收缩左边界还是右边界。方向搞反了程序不会报错但会返回一个看上去像那么回事的错误答案特别难发现。第三边界初值要选对。left 要初始化为一个必定不满足 check的值right 要初始化为一个必定满足 check的值。这两条如果有一边没保证最后返回的答案可能落在一个根本不可行的位置上。第四小心 check 内部的溢出。二分答案经常出现大数累加用 int 累加几万个 1e9 就直接爆了养成习惯用 long long 承接中间结果。这个坑我在做分割数组最大值的时候踩过数组总和超过 2^31 之后答案直接变成负数找了半天才反应过来是溢出。5.4 二分答案的复杂度估算二分答案的复杂度是判定函数复杂度 × 二分次数。如果判定函数是 O(n)值域大小是 V那总复杂度就是 O(n log V)。这个量级在绝大多数场景下都是安全的n 1e5V 1e9n log V 大约是 1e5 × 30 3e6一秒钟内绰绰有余。如果判定函数是 O(n log n)总复杂度就变成 O(n log n log V)大约 1e5 × 17 × 30 ≈ 5e7还在可控范围内但接近临界点需要斟酌常数。有一类题目判定函数本身就比较重比如涉及图论搜索或者动态规划这时候 log V 这个因子会显得很奢侈。遇到这种情况常见的优化方向是缩小答案值域比如发现答案一定是某些特定值的组合或者把判定函数优化到 O(n)。我个人的经验是先写出能过的版本再看测速结果是否真的卡不要一上来就做大优化很多时候想多了反而拖延。注意二分答案的答案值域不一定是连续的整数范围。有时候答案是实数那就用浮点二分加固定次数迭代有时候答案被限制在某个离散集合里那就先对集合排序再二分下标。判断值域的形状是动手之前必须做的一步。6. 常见问题与排查实录6.1 死循环排查速查表死循环是二分最经典的翻车方式症状是程序一直跑不完或者超时。下面这张表把最常见的原因列出来方便对照排查。症状可能原因修复方式程序卡住不结束mid 一直算到同一个位置检查更新时是否忘记 1/-1循环条件写反该用的地方用了明确区间类型再定条件区间永远不收缩left mid和right mid同时出现且 mid 不动至少一侧要能严格收缩mid 计算溢出写了(left right) / 2改成left (right - left) / 2数组越界left/right 初值算错闭区间 right n-1开区间 right n其中最隐蔽的是区间永远不收缩。假设你的判定是if (nums[mid] target) left mid; else right mid;当 left 和 right 相邻时 mid 会等于 left如果这时走的是left mid分支left 不动区间不收缩直接死循环。修复方式是至少保证一个分支能让区间变小比如left mid 1。这个坑我在写查找最后一个小于等于 target 的位置时反复踩后来养成习惯写完二分先手算一遍 left 和 right 相邻的情况。6.2 答案偏一位的原因分析比死循环更让人抓狂的是答案不对但程序正常结束。这种问题通常出在三个方面。第一是染色方向搞反把该归红区的条件归成了蓝区结果收敛到了相邻的另一个位置。判断方法很简单如果答案差 1把判定条件里的等号挪一下换往往就能修正但更重要的是回头想清楚等于 target 时应该算红区还是蓝区这个语义问题。第二是返回值的含义没对齐。开区间写法返回的是 right对应第一个满足条件的值如果你需要的是最后一个不满足条件的值那就应该返回 left。这两个值在相同时相差 1很容易混。我现在的做法是代码写完后写一行注释标明返回第一个 XXX 的位置让语义显式化减少误用。第三是初值没保证不变量。在二分答案里如果 left 初值选成了一个实际上满足 check 的值那最终收敛结果就会跑偏。我的习惯是在写代码前先在心里确认left 位置一定不满足 checkright 位置一定满足 check两个都确认过了再动手。这个习惯帮我省掉了大量 debug 时间。6.3 常见问题速查表除了上面两类还有一批高频问题这里一次性列清楚。问题现象排查方向处理建议结果总是差一位判定条件等号归属明确等于归红区还是蓝区空数组时崩溃未处理 n0进入二分前先判空返回目标不存在时行为错乱未校验命中位置二分后检查 nums[right]target重复元素时结果不稳定用了命中即返回模板改用边界模板求首次或末次位置浮点结果精度不够eps 设置不当改用固定迭代次数写法大输入时答案变负数int 溢出中间结果改用 long long这张表里的每一条我都亲身经历过。尤其是目标不存在时行为错乱这一条很多教材的模板在查不到时会返回 -1但因为边界收缩的原因返回的位置可能是一个有效但不相等的下标如果调用方没做校验直接使用就会拿到错误数据。养成二分完必须校验的习惯能挡掉一大类低级事故。6.4 我踩过的三个典型坑第一个坑是在旋转数组里用普通二分。旋转数组比如 [4, 5, 6, 1, 2, 3]整体不是有序的但存在一个断点。直接套有序数组的模板必然错。正确做法是先判断 mid 落在左半段还是右半段再决定往哪收缩。这个题型的核心不是二分本身而是怎么在两个有序段里选一个继续理解这一点之后代码就是顺理成章的事。第二个坑是二分答案时忘了 check 里的边界。有一次做运送包裹的最少容量这道题check 函数里我算累加和时只在超过容量时重置结果忘了处理单个包裹本身超过容量的情况导致二分收敛到一个根本不能用的容量。这类逻辑错误的共同点是局部看似合理整体不自洽是靠肉眼看代码很难发现的必须靠构造边界用例来暴露。我后来形成的习惯是写完 check 先用极端输入测一下全是最小值、全是最大值、只有一个元素。第三个坑是在二分查找里对非有序数组动心思。有段时间我研究能否在部分有序的数组里用二分结果写出了一堆只在特例下成立的花架子代码。后来明白了一件事二分的适用性由单调性质决定不由数组看起来整不整齐决定。如果数据没有可依赖的单调结构就不要硬凑二分换个思路比如哈希表、前缀和往往更简单可靠。这个教训让我在选算法时先问单调性在哪而不是这题像不像二分题。最后分享一个我自己验证二分代码的小技巧写完之后用一个长度为 1 的数组比如只有 [target]、一个长度为 2 的数组[target, target] 和 [target-1, target]、一个所有元素都小于 target 的数组、一个所有元素都大于 target 的数组这四个极端用例手动跑一遍。能扛过这四种情况的二分基本就稳了。这套小用例我现在已经形成了条件反射几乎不用思考就能报出来推荐你也把它练成肌肉记忆它比任何模板都更值钱。二分算法这东西写到最后你会发现真正的门槛不在代码本身而在把问题翻译成单调性这一步。翻译对了模板随便挑一个都能过翻译错了模板再漂亮也是白搭。建议你在刷题的时候不要只看题解里的那段二分先去想这题的单调性是什么、边界代表什么语义想通了再落笔。这个思路转换的过程比多做十道同类型题目有价值得多。