先说个真实经历。我当年第一次接触二分法的时候觉得这玩意儿太简单了——有序数组里找个数三个分支一写完事。直到某次在 LeetCode 上遇到一道需要写寻找第一个大于等于 target 的位置的题我按照所谓背下来的模板改来改去先是死循环再是越界后来返回的下标错了一位中间还夹杂着 mid 的计算方式对不对的自我怀疑。连续改了四五遍才跑通那一刻我才意识到二分写不对不是手生是根本没搞懂自己维护的区间到底是什么。所以这篇东西不打算写成那种背过就完事的模板文。我想把我后来在二分法上真正想明白的东西以及那些最容易翻车的细节用学习笔记的形式整理出来。不论你是在准备校招机试、刷 LeetCode还是打算法竞赛只要你需要亲手写二分这篇文章都值得慢慢读一遍。1. 先把最熟悉的模板写清楚左闭右闭写法为什么能自洽1.1 模板代码与两个关键条件我们最常见的二分查找是在升序数组里找一个确定的值。标准写法长这样int binarySearch(vectorint a, int target) { int l 0, r a.size() - 1; while (l r) { int mid l (r - l) / 2; if (a[mid] target) return mid; else if (a[mid] target) l mid 1; else r mid - 1; } return -1; }这段代码几乎所有教材都会给。但真问你三个问题很多人未必答得利索为什么循环条件是l r而不是l r为什么l要更新成mid 1r要更新成mid - 1循环结束后l和r到底停在哪里这三个问题要是答不上来后面遇到任何二分变形题都会发虚。我在学习笔记里把答案总结成一句话你维护的搜索区间是[l, r]一个闭区间而每次循环你要做的是排除掉mid这个唯一已经被检查过的位置。1.2 用搜索区间概念理解边界更新理解了搜索区间上面三个问题就全通了。一开始[l, r]是整个数组目标是找target。mid是当前区间中间的位置这一步是必须检查的。如果a[mid] target直接返回不需要再讨论。关键在a[mid] target这个分支。既然a[mid]已经比target小了又因为数组升序mid以及mid左边所有元素全都比target小它们都不可能成为答案。于是区间左边界可以直接收缩到mid 1也就是l mid 1。反过来a[mid] target时mid以及它右边所有元素都比target大都不可能成为答案右边界收缩到mid - 1。看到没有l mid 1和r mid - 1之所以要加一减一是因为mid已经被比较过了它一定要被排除出新的搜索区间。如果你写成l mid或者r mid那mid就永远留在区间里一旦遇到某些边界情况后面会细说循环就再也跳不出来死循环就是这么来的。再回来看while (l r)。这个条件其实是在表达只要搜索区间不为空就继续搜。当l r时区间里还剩最后一个元素它还没被检查过所以必须再进一次循环把它处理掉。如果这里写成l r那最后一个元素会成为漏网之鱼循环退出后你还得额外判断一下a[l]等不等于target逻辑反而绕。1.3 循环结束后 l 和 r 各在哪那循环结束l r之后l和r分别是多少我后来在笔记里画了很多遍图才彻底记住当 target 不在数组里时循环结束后l指向第一个大于 target 的位置r指向最后一个小于 target 的位置。换句话说l就是target如果要插入数组、数组仍然有序的话它应该待的下标位置也就是 C 里lower_bound的返回值。举个例子数组是[1, 3, 5, 7, 9]target 是 6。模拟一遍初始l0, r4, mid2, a[2]5 6所以l3区间[3,4]mid3, a[3]7 6所以r2此时l3, r2l r循环退出结果l3指向数组中的 7确实是第一个大于 6 的位置这个性质特别重要。很多二分变形题不要求你返回-1表示不存在而是要求返回插入位置或者第一个大于等于某值的位置而这些东西恰恰就是循环结束后的l。你只要把上面的模板稍微改一下就能变成一个通用的寻找下界函数int lowerBound(vectorint a, int target) { int l 0, r a.size() - 1; while (l r) { int mid l (r - l) / 2; if (a[mid] target) l mid 1; else r mid - 1; } return l; }和第一个模板的区别只是把a[mid] target这个分支删掉了。相等的时候我们不返回而是把它归入右边界收缩那一类因为我们想找的是边界而不是某个具体的相等位置。l最终指向第一个不小于 target 的位置这正好就是下界。这个模板我强烈建议你在笔记里单独记一栏它是后面所有二分变体的地基。2. 三种主流写法的不变式对比左闭右开、开区间都从哪来2.1 左闭右开写法除了闭区间写法另一种非常常见的写法是左闭右开也就是区间是[l, r)。int lowerBoundLeftOpen(vectorint a, int target) { int l 0, r a.size(); // 注意 r 初始是 n不是 n-1 while (l r) { int mid l (r - l) / 2; if (a[mid] target) l mid 1; else r mid; } return l; // l r }这个写法有几个肉眼可见的不同r初始化为n而不是n-1因为区间是左闭右开r本身不在区间内循环条件是l r当l r时区间为空收缩右边界时直接r mid而不是r mid - 1为什么r mid而不是r mid - 1因为右开区间的终点r本来就不包含在搜索范围里。我们要收缩的是从 mid 到 r 这一整块右侧区间而收缩之后新区间是[l, r_new)这个区间必须不包含 mid因为 mid 已经被比较过了。如果令r_new mid新区间[l, mid)确实不含 mid如果令r_new mid - 1区间会变窄但更关键的是可能丢掉一些没检查过且可能是答案的元素。所以在左闭右开写法里r mid才是和不变式匹配的操作。2.2 开区间写法l -1, r n 的语义优势还有一种写法区间的两端都是开的(l, r)。初始让l -1、r n表示左右两端都不包含在搜索范围内。int lowerBoundOpenInterval(vectorint a, int target) { int l -1, r a.size(); while (l 1 r) { int mid l (r - l) / 2; if (a[mid] target) l mid; else r mid; } return r; }循环结束时l是最后一个满足a[l] target的位置r是第一个满足a[r] target的位置。这两个变量的语义非常清晰一个代表小于 target 的最后一个元素下标一个代表大于等于 target 的第一个元素下标。我也见过不少竞赛选手特别偏爱这个写法因为它不需要纠结l和r谁有偏移最后返回谁看语义就行。缺点是对新手来说l -1这个初始值看起来有点反直觉毕竟数组下标没有负的。但其实这里l不一定要是合法下标它只是一个哨兵方便表达左侧还没有任何元素满足条件这个状态。2.3 为什么建议固定一种模板而不是每次现场推导学习二分法最容易踩的坑之一就是学了好几种写法之后每次做题都在纠结这次到底用哪种循环条件写还是收缩边界是mid 1还是mid本来思路就乱一纠结更乱。我的建议是选一种你最能讲清楚不变式的写法长期固定使用。我个人固定的是第一种闭区间写法因为它最直观和大多数人最先学的教材一致出问题时也好跟人讨论。但左闭右开写法在 C 标准库里大量使用而且处理数组为空、target 比所有元素都大的场景时特别自然返回n作为插入位置不越界这也是为什么我会专门把它拿出来分析。开区间写法则是竞赛里追求效率的人常用的。三种没有绝对优劣关键是你能不能把它的区间语义说清楚。如果你还在摇摆我给你一个可操作的建议先熟练掌握闭区间写法然后花一个下午把左闭右开写法对照着背下来因为 STL 的lower_bound、upper_bound以及很多面试题的官方题解都默认用左闭右开。再把开区间写法当成进阶理解材料读懂它的l和r语义之后你对二分法的理解会上一个台阶。还有个小技巧无论用哪种写法写完代码后在旁边注释一行当前不变式是什么。比如闭区间写法的注释是// [l, r] 中可能包含答案左闭右开的注释是// [l, r) 中可能包含答案。等排查 bug 的时候你会感谢这一行注释的。3. 死循环、溢出和返回值错位二分翻车主要翻在这三个地方3.1 l mid 导致的死循环及其上取整修正死循环是二分法最经典的翻车现场而绝大多数死循环都出在l mid这个赋值上。我拿一个实际场景讲要求找到最后一个小于等于 target 的位置。你可能觉得这不就是把二分模板改改吗于是写成int lastLe(vectorint a, int target) { int l 0, r a.size() - 1; while (l r) { int mid (l r) / 2; // 向下取整 if (a[mid] target) l mid; else r mid - 1; } return l; }假设数组是[1, 3, 5]target 是 4。第一次循环l0, r2, mid1, a[1]3 4于是l mid 1。第二次循环l1, r2, mid1a[1]3 4又l mid 1。第三次循环l1, r2……完了l 永远不动死循环。问题出在哪当区间只剩两个元素也就是l和r相邻时如果mid向下取整mid会落到l上。这时如果条件成立导致l mid那 l 根本没变区间没有收缩循环条件还成立于是无限循环。解决办法是让mid改成向上取整int mid (l r 1) / 2; // 或 l (r - l 1) / 2还是刚才的例子。l1, r2, mid(121)/22, a[2]5 4走r mid - 1 1循环结束返回 l1答案正确。我把这个规律总结成笔记里的一个口诀如果你在循环体里写了l mid那 mid 一定要向上取整如果你写了r mid那 mid 通常可以向下取整。这个口诀不是万能的但大多数场景下能救你一命。本质原因就是l mid会把 l 和 mid 绑定如果 mid 取不到比 l 更大的值区间就永远不会收缩。3.2 mid 计算溢出l (r - l) / 2 的由来和适用范围这又是二分法里一个被问了无数次但很多人知其然不知其所以然的问题为什么不直接写mid (l r) / 2而要写mid l (r - l) / 2原因是l r可能溢出。在 C、Java 这类语言里如果l和r都是很大的 int比如都接近 2^31 - 1那l r会超过 int 能表示的最大值变成负数mid 自然就错了。而l (r - l) / 2先算r - l这个差值一定小于等于数组长度通常不会溢出然后再加上 l结果一定落在[l, r]范围内安全。不过这里我要补充一点这个技巧的适用范围是l和r都是非负数或者至少同号。如果l可能是负数比如开区间写法里l -1l (r - l) / 2仍然安全因为r - l更小但如果直接写(l r) / 2负数加上大正数也可能出问题。所以统一建议只要有整数溢出的可能就写成l (r - l) / 2没坏处。Python 用户可能觉得这条无所谓因为 Python 整数是任意精度的。但如果你后面学 C、Java 或者写 Rust这条就很重要了。而且面试官特别喜欢拿这个点来考你说得出原理印象分会好很多。3.3 循环结束后到底返回 l 还是 r第三个高频翻车点是循环结束后返回值搞错。这个问题只会在用while (l r)的写法里出现因为闭区间写法l和r分得很开你一般不会搞混。左闭右开写法里循环结束的标志是l r所以返回l和返回r一样问题不大。但开区间写法里循环结束时l和r是两个不同的值l是最后一个满足左边条件的下标r是第一个满足右边条件的下标。如果你没想清楚题目要什么可能就返回错了。我举个例子用开区间写法查找第一个大于等于 target 的位置循环结束后应该返回r。但如果题目改成最后一个小于 target 的位置那就要返回l。这两个值只差一但答案天差地别。我自己的排查习惯是在写任何二分题之前先在注释里写清楚我要返回的是什么然后根据不变式推导返回哪个变量。比如开区间模板中l永远指向不满足条件的那一侧r指向满足条件的那一侧。你要是记不清就退回去想区间(l, r)一开始是全体结束时l和r相邻中间没有任何未检查元素了那答案要么是l要么是r看它属于哪一侧。3.4 一个真实的排查过程这些坑我当年是一次次踩过来的。记得有一次做一道搜索旋转排序数组的题数组是[4,5,6,7,0,1,2]让我找 target。我想当然地写了个闭区间二分mid 计算用的是(lr)/2条件分支里还掺杂了l mid。结果一跑样例直接超时。当时我干了一件事在循环里打印l, r, mid三个变量。结果发现当l5, r6时mid永远等于 5而a[5]1小于 target代码执行lmidl 永远是 5区间永远不收缩。那一瞬间我就明白了问题不是旋转数组的边界判断而是l mid配了向下取整。改成mid (l r 1) / 2并在该分支用上取整之后样例瞬间通过。之后我再也没小看过二分法的边界细节。4. 二分不止查找从有序数组到二分答案的通用套路4.1 把求最值拆成判定可行check(x) 与单调性学二分查找的时候我们面对的是一个已经有序的数组。但随着刷题变多你会发现二分真正的威力远不止有序数组查数而在于对答案进行二分——通常叫二分答案。二分答案的核心思想是不直接求最优解而是猜一个答案 x再写一个函数check(x)判断 x 是否可行最后把所有可行/不可行的边界二出来。这里有一个必须满足的前提check(x)关于 x 要有单调性。什么叫单调性以最大最小值类问题为例x 表示允许的最大值是这么多那 x 越大方案越容易可行x 越小方案越难可行。这种越大越容易/越小越容易的性质就是单调性。我看到很多初学者最常犯的错误就是拿到题连单调性都没分析直接套二分模板开写。最后结果当然是错的而且错得莫名其妙。所以在我的学习笔记里我把先证明 check 单调写成了红色警告。具体怎么验证拿几个 x 从小到大代入 check看结果是不是一串 false 后面跟着一串 true或者反过来。如果是才能放心二分。4.2 一个最小化最大值的例子如何把原问题转化为判定我最喜欢用来讲二分答案的例子是分割数组的最大值给定一个非负整数数组和一个整数 k需要把数组切成 k 个连续子数组问这 k 个子数组各自和的最大值最小可以是多少。直接求最大值最小很抽象但转换成判定问题就清楚多了给定一个 x能不能让数组被切成若干段使得每一段的和都不超过 x并且段数不超过 k这个 check 函数一点都不难写贪心扫一遍就行bool check(vectorint a, int k, long long x) { int cnt 1; long long sum 0; for (int v : a) { if (sum v x) { cnt; sum v; if (cnt k) return false; } else { sum v; } } return true; }然后二分答案下界是所有元素的最大值因为每段至少要包含一个元素上界是数组总和long long l *max_element(a.begin(), a.end()); long long r accumulate(a.begin(), a.end(), 0LL); while (l r) { long long mid (l r) / 2; if (check(a, k, mid)) r mid; else l mid 1; } return l;你看这就是把求最值变成了判断可不可行然后对 x 做二分。这里 check 的单调性也很直观x 越大每段和的上限越大越容易用不超过 k 段完成分割所以 check(mid) 的结果是小 x 全是 false大 x 全是 true正好可以二分。这类最小值最大或者最大值最小的问题在面试和竞赛里非常常见。你做多了就会发现它们几乎都有一个共同特征如果直接贪心求最优解很困难但给定一个可行解去验证却很容易那就大概率是二分答案的题。4.3 浮点数二分的精度处理和迭代次数二分答案不仅能作用在整数上还能作用在浮点数上。比如给一个实数求它的立方根精确到小数点后几位。整数二分写惯了的人第一次写浮点数二分容易陷入精度怎么设的泥潭。我的建议是不要用r - l eps这种判断作为循环条件直接 for 循环迭代固定次数。double cubeRoot(double x) { double l 0, r max(1.0, x); for (int i 0; i 100; i) { double mid (l r) / 2; if (mid * mid * mid x) l mid; else r mid; } return (l r) / 2; }为什么固定 100 次因为每迭代一次区间宽度减半100 次之后区间宽度是初始宽度的 2^(-100)这个数量级已经远超 double 的精度。所以与其纠结 eps 设 1e-7 还是 1e-9不如直接迭代一个能保证精度的次数省心。如果你真要写 eps也记得不要设得太小否则可能因为浮点数表示误差陷入死循环。比如目标精度是 1e-6你 eps 设 1e-8 可能没事设 1e-12 就可能出问题。固定迭代次数完全没有这个烦恼这也是我在实际做题里更推荐的方式。4.4 值域二分与索引二分的本质区别聊到这里我想把两个概念区分开索引二分二分的是数组下标mid是一个下标。要求数组本身有序或者能按某个规则单调。我们前面讲的所有查找都是在做索引二分。值域二分二分的是答案的值域mid是一个猜测的答案。数组不一定有序有时候甚至没有数组只有一个 check 函数。上面的分割数组最大值就是值域二分。这个区别为什么重要因为很多人学完二分查找后会下意识认为二分必须数组有序。但值域二分完全不需要数组有序它只需要 check 函数单调。我见过有人遇到一道数据范围是10^9的题就慌了觉得没法枚举其实只要你 check 函数写得出来二分答案的区间可以很大哪怕l0, r1e18都没问题因为每次检查都是 O(n) 或 O(log n)乘以一个几十次的二分照样跑得飞快。掌握了这个本质区别你才算真正把二分从查找工具升级成了优化工具。5. 那些就差一点点的小坑实用排查清单与个人习惯5.1 边界用例自测清单代码写完之后怎么快速判断二分写没写对我强烈建议在提交前跑一遍下面这张清单里的用例。这些用例能覆盖大部分死循环和越界问题。用例类型数组target期望结果以第一个 target 的下标为例空数组[]50插入位置单元素target 小[3]10单元素target 相等[3]30单元素target 大[3]51两个元素target 落在中间[2, 4]31重复元素找下界[1, 2, 2, 2, 3]21重复元素找上界[1, 2, 2, 2, 3]24第一个 2 的下标target 小于所有元素[2, 4, 6]10target 大于所有元素[2, 4, 6]73如果这些用例都能过说明你的二分至少没有大方向的问题。特别是两个元素和重复元素这两个最能试出l mid死循环和返回值错位。5.2 STL 的 lower_bound / upper_bound 与手写二分的关系聊到二分查找C 程序员绕不开std::lower_bound和std::upper_bound。以前我面试时问候选人你手写过二分吗十有八九说写过但再问那lower_bound和你手写的二分有啥关系很多人就开始含糊了。其实它们的关系很简单std::lower_bound(begin, end, value)返回第一个 value的位置等价于我们第二节里的左闭右开模板。std::upper_bound(begin, end, value)返回第一个 value的位置等价于把 left open 模板里的判断从if (a[mid] target)改成if (a[mid] target)int upperBound(vectorint a, int target) { int l 0, r a.size(); while (l r) { int mid l (r - l) / 2; if (a[mid] target) l mid 1; else r mid; } return l; }有了这两个函数你可以很方便地统计有序数组中等于某个值的元素个数count upper_bound(...) - lower_bound(...)。这也是很多人在 LeetCode 上解有序数组里找某个数出现的次数这类题的首选方案。我一般建议比赛或面试默认库函数能用就用但你必须能用手写方式解释清楚它的内部行为。因为面试官不一定要求你用库函数他们更想看你会不会从底层推导。而且有些场景库函数确实用不了比如自定义二维矩阵上的二分这时候手写能力就是硬通货。5.3 调试二分的一点个人习惯最后分享几个我自己调试二分的习惯不算什么高深技巧但每次都能帮我快速定位问题。第一先用小数组手工推一遍再跑程序。写一个长度 5 到 7 的数组在纸上写下每一步的l, r, mid、判断条件和更新结果。推到第三次循环如果还没发现问题再用程序输出的l, r, mid跟纸面对照。这一步看着笨但特别有效因为二分的问题几乎都出在前几层循环里手工推一遍基本能发现是区间更新还是返回值的问题。第二在循环里临时加打印。不用打印太多就打印三个变量l, r, mid。死循环的话你会看到某两个值反复不变返回值错位的话你会看到最后一步的l和r停的位置和预期差一个。第三写完之后问自己两句话这个循环结束时为什么 l 和 r 一定收敛到了正确答案如果 target 不在数组里我的代码会怎样 这两句话能逼你想清楚不变式而不是凭感觉背模板。第四注意下标从 0 还是从 1 开始。很多算法题的下标是 1-based比如某些线段树题目如果你把 0-based 的二分模板直接套上去返回的结果需要加一或减一极其容易错位。我一般会在拿到题目时先在纸上标出输入下标从几开始输出要求从几开始避免写到一半把自己绕晕。写在笔记末尾的一句话二分法这玩意儿表面看就几行代码实际写对全靠对区间不变式的理解。我学它踩了太多坑也见过太多人在同样的坑里反复打转所以这篇笔记写得很碎、很啰嗦但每个点都是我真实撞过南墙之后总结出来的。如果你现在写二分还不太稳别急着刷量先把我上面这几节的内容对着代码逐条过一遍特别是那个死循环三要素——l mid配上取整、闭区间还是开区间、循环结束返回谁——想通了二分的题基本就难不倒你了。