C++二分查找细节敲定：从边界条件到树状数组实战

二分这种东西写起来感觉就几行真正敢说完全拿捏的人却没几个。哪怕从面试到工程实战都绕不开它很多人依然会在边界条件上反复横跳不是死循环就是答案差一位。我早些年也栽过不少跟头后来把C里二分的那些细节规则彻底捋了一遍才算是真正稳下来。这篇就把我对二分细节敲定的理解一次性说透从最基础的写法到树状数组上的特殊玩法再到工程落地时的调试习惯全给你盘明白。1. 整体设计思路与细节根源1.1 为什么二分写着简单错起来却要命二分查找的核心思想一句话就能讲完在一个有序区间里每次比较中间值排除掉一半不可能的区域把搜索范围缩到足够小。逻辑上无懈可击但一旦落到代码上问题就全出来了。最典型的几个“翻车点”包括while循环里到底该写left right还是left rightmid到底该不该加1更新区间时left和right究竟谁该等于mid谁该等于mid 1或mid - 1。我见过太多人在这些细节上凭感觉写结果要么死循环要么区间收缩不到正确位置。说实话这真不是智商问题而是二分这东西天然有“规则内隐”的特征——你看那些教科书里的模板边界条件往往是基于特定的区间定义和循环不变量推导出来的如果没搞懂背后的不变量只是机械地背一个模板换个场景立刻报废。我自己后来总结出一条经验写二分之前先花十秒钟想清楚两个问题。第一你维护的区间是左闭右开[left, right)还是左闭右闭[left, right]。第二你的循环退出条件是什么退出之后left或者right指向的到底是哪个位置。这两个问题一旦敲定后面所有的边界处理都是机械推导根本不需要每次重新猜。1.2 从区间定义推导细节而不是背模板很多人学二分喜欢背模板背那种“万能二分”的写法。我只能说模板可以背但不能只背一个。因为实际需求千变万化找第一个等于目标的位置、找最后一个等于目标的位置、找第一个大于等于目标的位置、找最后一个小于等于目标的位置……每一种需求的边界细节都有微妙差别。我的建议是把“维护的区间”看作二分的真正主角。比如经典写法中如果你维护的是[left, right]闭区间那么初始left 0right n - 1循环条件就是left right因为当left right时区间才真正为空。而如果维护的是[left, right)半开区间初始right n循环条件就得是left right因为当left right时区间已经为空。这两种写法都能做对但混用就全乱了。我自己实际写代码时绝大多数情况倾向于用[left, right)半开区间原因有两点一是它和C标准库的迭代器区间风格一致begin()和end()本身就是左闭右开[first, last)已经约定俗成二是半开区间在表示空区间、表示“插入位置”这类需求时特别自然不需要额外处理-1或1的边界。1.3 敲定规则的第一步明确你的搜索语义在动笔之前还有一件事比区间定义更前置那就是搞清楚你要的“答案”到底是什么语义。是要找“值等于target的下标”还是“第一个不小于target的位置”还是“最后一个不大于target的位置”语义不同同一种区间定义写出来的代码也会不一样。我建议把常见语义整理成一张速查表这是我自己每次写二分之前都会在心里过的目标语义典型场景区间定义建议返回位置精确查找值等于target数组查值闭区间或半开区间均可找到返回下标找不到返回-1找第一个target的位置lower_bound半开区间最自然返回第一个满足条件的位置找第一个target的位置upper_bound半开区间最自然返回第一个大于target的位置找最后一个target的位置前缀边界查询闭区间或半开区间均可返回最后一个满足条件的位置有了这张表你写二分时的每一步“敲定”都有了依据而不是靠感觉。2. 核心细节解析边界、中点和循环不变量2.1 mid的取整方向与死循环的根源mid的计算看起来最简单left (right - left) / 2但取整方向其实大有讲究。C整数除法是向零取整对于非负数来说就是向下取整所以mid天然偏向左边。这个“偏向左边”在很多场景下没问题但在某些区间更新规则下会直接导致死循环。最经典的死循环场景是这样的当你维护[left, right)区间且right left 1时mid left (right - left) / 2算出来等于left。如果这时你的更新规则是“满足条件时left mid”那么区间就永远不会收缩死循环了。反过来如果你在某些场景下需要mid偏向右边就得写成mid left (right - left 1) / 2也就是向上取整。我记得有一道很经典的题——寻找左边界和右边界两种写法刚好对应这两种mid取整方向。找左边界时left mid 1、right mid的组合配合向下取整mid永远不会死循环。而找右边界时如果写left mid、right mid - 1就必须配合向上取整的mid否则在right left 1时直接卡死。关于这一点我特意做了一个小实验代码很简单但结果很能说明问题#include iostream #include vector int main() { std::vectorint arr {1, 2, 3, 4, 5}; int target 3; int left 0, right arr.size(); while (left right) { int mid left (right - left) / 2; if (arr[mid] target) { left mid 1; // 左边界收缩安全 } else { right mid; // 右边界收缩配合向下取整 } } std::cout 找到的位置: left std::endl; return 0; }这段代码是安全的。如果把left mid 1改成left mid把right mid改成right mid - 1再配合向下取整当区间缩到[2, 3)时就会原地打转。这就是mid取整方向与区间更新规则不匹配导致的经典死循环。2.2 循环不变量写对二分的唯一方法论聊二分细节不提循环不变量等于没聊。所谓循环不变量就是你在循环过程中始终保持的一个性质它决定了你每一步更新之后答案仍然在你维护的区间内。举个例子我写lower_bound找第一个大于等于target的位置时维护的不变量是left左侧的所有元素都严格小于targetright右侧的所有元素都大于等于target。初始时left 0左侧没有元素这个性质成立right n右侧没有元素也成立。每次循环比较arr[mid]与target如果arr[mid] target说明mid及其左侧都不能是答案所以left mid 1不变量依然成立否则right mid说明mid可能是答案但右边不会是第一个收缩右边界不变量依然成立。循环结束时left right整个搜索区间为空而答案就在left位置。看一旦把不变量写在纸上连代码都不需要猜边界的每一步都是逻辑推导出来的。我强烈建议所有被二分困扰过的人在写每一道二分题、每一段二分代码之前先在注释里把不变量写清楚。工程上这也有实际价值——别人review你代码的时候看到不变量注释一眼就能确认你的逻辑没缺陷。2.3 防溢出与性能取舍mid计算的工程细节mid (left right) / 2这种写法在面试里说说还行工程上我基本不用因为left right存在溢出风险。虽然很多场景下left和right都是数组下标int溢出需要数组大到离谱但一旦你写的是通用模板或者处理的是迭代器差值很大的场景溢出就变成真实风险了。所以我一律写成mid left (right - left) / 2把加法换成减法从根本上规避溢出。这个习惯成本极低但能把一类潜在bug直接消灭在源头。另外在性能敏感的场合有人会把除以2改成位运算 1但我个人建议除非你确实在写那种被压榨到极致的性能关键代码否则别这么做。现代编译器对除以常量的优化已经非常到位写成位运算反而降低可读性维护起来也更容易犯错。还有一种情况需要格外注意就是left (right - left) / 2在right - left得到的是size_t这类无符号类型时运算结果会变成无符号这可能带来意外行为。我通常在二分函数里显式把区间端点转成有符号类型比如int或ptrdiff_t宁可多写一行强转也不愿留一个不容易察觉的类型隐患。3. 实操过程从标准库到树状数组上二分的完整实现3.1 标准库的二分lower_bound与upper_bound的正确打开方式C标准库早就提供了现成的二分实现std::lower_bound、std::upper_bound、std::binary_search。这几个函数放在algorithm头文件里内部实现基本是教科书级别的二分。但很多人直接用它们时还是会出错原因在于没搞懂它们返回的迭代器语义。我用一个简单的例子说明#include iostream #include vector #include algorithm int main() { std::vectorint arr {1, 2, 2, 2, 3, 4, 5}; auto it1 std::lower_bound(arr.begin(), arr.end(), 2); auto it2 std::upper_bound(arr.begin(), arr.end(), 2); std::cout 第一个2的位置: (it1 - arr.begin()) std::endl; std::cout 第一个2的位置: (it2 - arr.begin()) std::endl; std::cout 等于2的元素个数: (it2 - it1) std::endl; return 0; }输出结果分别是1、4、3完全符合语义。这里能看到lower_bound和upper_bound联合起来能直接算出某个值在有序数组中的重复区间长度。这是它们最经典的配合玩法在统计频次、范围查询等场景特别实用。std::binary_search返回bool表示是否存在目标值但它内部就是调用lower_bound判断迭代器是否指向目标值并不比直接调用lower_bound更高效。所以我很少用binary_search因为它只告诉“有没有”不告诉“在哪里”大多数工程场景我们恰恰需要“在哪里”。3.2 手写二分的两个黄金模板虽然标准库很香但有些场景必须手写二分比如在复杂结构上二分、在自定义判断条件下二分。这里分享两个我实测下来最稳的模板一个用于“找左边界”一个用于“找右边界”都基于半开区间[left, right)和明确的循环不变量。先看第一个模板找第一个满足条件的位置条件用函数bool check(int idx)抽象。// 找第一个满足check的位置 // 不变量: left左侧全部不满足, right右侧全部满足 int binary_search_left(int left, int right, const std::functionbool(int) check) { while (left right) { int mid left (right - left) / 2; // 向下取整 if (check(mid)) { right mid; // mid可能是答案, 但答案不可能在mid右侧 } else { left mid 1; // mid不满足, 答案不可能在mid及左侧 } } return left; // 此时 left right, 就是第一个满足条件的位置 }这个模板的精髓在于check(mid)为true时收缩右边界到mid为false时收缩左边界到mid 1。用向下取整的mid配合left mid 1永远不会死循环因为每次循环区间长度至少减1。再看第二个模板找最后一个满足条件的位置。// 找最后一个满足check的位置 // 不变量: left左侧全部满足, right右侧全部不满足 int binary_search_right(int left, int right, const std::functionbool(int) check) { while (left right) { int mid left (right - left 1) / 2; // 向上取整 if (check(mid)) { left mid; // mid满足, 答案不可能在mid左侧 } else { right mid - 1; // mid不满足, 答案不可能在mid及右侧 } } return left; // 此时 left right, 就是最后一个满足条件的位置 }注意这里的mid用了向上取整这是关键。因为在right left 1时如果还用向下取整mid left一旦check(mid)为true就会执行left mid区间不收缩死循环。向上取整后mid right无论哪个分支都能让区间变短。这两个模板我建议直接背下来然后花十分钟分别用几个典型场景验证一下比如在{1, 2, 2, 2, 3}里找第一个2和最后一个2一旦确认逻辑没问题后面所有的二分题都可以往里套不用每次重新推导。3.3 进阶玩法树状数组上的二分装完基础模板再来点硬核的——树状数组上二分。树状数组Fenwick Tree常用来维护前缀和支持单点修改和前缀和查询。常规查询某个前缀和达成什么位置时需要O(log n)的二分套O(log n)的查询总复杂度O(log² n)。而树状数组上二分可以把这玩意儿压到O(log n)原理是利用树状数组的二进制结构直接倍增定位。做法是从最高位开始往下枚举维护一个pos表示当前已经确定的位置sum表示pos位置的前缀和。初始pos 0sum 0。从大到小枚举每一位从LOG - 1到0如果pos (1 k) n且sum tree[pos (1 k)] target就更新pos (1 k)、sum tree[pos]。循环结束后pos就是最后一个前缀和小于target的位置pos 1就是第一个前缀和大于等于target的位置。直接看代码更清楚#include iostream #include vector class Fenwick { public: explicit Fenwick(int n) : tree(n 1, 0), n(n) {} void add(int idx, int delta) { while (idx n) { tree[idx] delta; idx idx -idx; } } // 找最小的 idx 使得前缀和 target // 前提: 树状数组中所有元素非负, 前缀和单调不减 int lower_bound_prefix_sum(int target) { int pos 0; int sum 0; // LOG 取 20 足够覆盖 1e6 量级, 更大量级可以按需调整 for (int k 20; k 0; --k) { int next pos (1 k); if (next n sum tree[next] target) { sum tree[next]; pos next; } } return pos 1; } private: std::vectorint tree; int n; }; int main() { Fenwick fw(10); for (int i 1; i 5; i) { fw.add(i, i); // 位置i的值设为i } // 前缀和: 1, 3, 6, 10, 15 std::cout 第一个前缀和6的位置: fw.lower_bound_prefix_sum(6) std::endl; std::cout 第一个前缀和7的位置: fw.lower_bound_prefix_sum(7) std::endl; std::cout 第一个前缀和16的位置: fw.lower_bound_prefix_sum(16) std::endl; return 0; }这里add(i, i)是把位置i的值设为i前缀和依次是1、3、6、10、15。lower_bound_prefix_sum(6)返回3lower_bound_prefix_sum(7)返回4lower_bound_prefix_sum(16)返回11超出范围时返回n1。结果完全符合预期。注意前提条件树状数组里存的必须是单调不减的前缀和序列也就是所有单点值非负。如果存在负值前缀和不单调这个倍增法直接失效。这一点是树状数组上二分最大的约束工程上遇到带负权值的需求时得换线段树加二分或者用其他数据结构。3.4 浮点数二分的注意事项除了整数二分浮点数二分也经常被忽视。浮点数二分没有“死循环”问题因为循环条件一般是right - left eps但它的坑在精度控制上。eps设太大结果不够精确设太小循环次数暴增甚至可能因为浮点精度问题永远达不到条件而死循环。我的一般做法是不把eps设成固定值而是设定固定的迭代次数比如100次。100次二分可以把一个长度1的区间压缩到2的-100次方对绝大多数浮点场景都绰绰有余而且完全规避了eps设置不当导致的死循环。double binary_search_float(double left, double right, const std::functiondouble(double) func) { for (int i 0; i 100; i) { double mid left (right - left) / 2.0; if (func(mid) 0) { right mid; } else { left mid; } } return left; }循环100次而不是用while (right - left eps)是我从实际项目中总结出来的一个细节它让代码行为完全可预测不会因为目标函数的性质导致循环次数失控。代价只是多跑几十次迭代在浮点二分场景下这点开销完全可以忽略。4. 常见问题与排查技巧实录4.1 死循环的快速定位与修复方法写二分最常遇见的错误就是死循环。程序卡住不动CtrlC中断后发现卡在while循环里。快速定位的思路其实很固定把区间长度变化过程打印出来或者直接在循环里输出left、right、mid三个值。我用过一个很笨但有效的方法在while循环里加打印如果某次迭代left和right都没变化说明区间没有收缩死循环的根源就在这一步。然后检查两个地方一是mid的取整方向二是区间更新时哪个分支没有让区间长度减少。按照我的经验90%的死循环都是“向下取整的mid配合了left mid”或“向上取整的mid配合了right mid”这两对组合全是雷。4.2 答案差一位边界返回值永远要用真实案例验证二分返回值的差一问题比死循环隐蔽得多因为程序能跑完结果却不对。我自己踩过的坑主要出在“答案在左边界还是右边界”的语义混淆。比如找第一个大于等于target的位置有人会返回left有人会返回right在循环结束时left right理论上一样但如果循环条件或区间更新写错了这俩就可能差1。我的排查方法是写一个简单的有序数组把每个可能的目标值都测一遍用assert断言结果和标准库lower_bound一致。像我这种习惯用半开区间的人几乎每写一段手写二分都会顺手加一个对照标准库的验证用例。别嫌麻烦二分这东西太容易被细节坑了能自动验证就自动验证。4.3 二分答案应用中的check函数设计陷阱二分的应用不只在数组里找值还有一大类叫“二分答案”——在一个单调的可行性函数上二分找到满足条件的边界值。比如“最小化最大值”问题就是二分化可行性。这种场景下真正的细节难点不再是二分本身而是check函数的实现。我踩过的一个典型坑是check函数里忘了恢复修改的状态。比如某道题需要dfs验证某种放置方案是否可行dfs过程会修改全局状态如果check返回false后没有恢复状态下一次check就全乱了。排查这类bug特别痛苦因为问题不在二分模板里而在check函数的副作用上。我的建议是设计check函数时坚持一个原则——要么没有副作用要么所有修改必须在使用完后恢复原状。最好把check写成纯函数只返回true或false不改变任何外部状态。4.4 调试技巧把二分过程可视化除了打印中间变量还有一个很高效的调试技巧用树状图把二分区间收缩过程画出来。我一般会把left、right、mid以及当前比较结果记录在一个列表里跑完之后对着列表手工推演一遍定位具体是哪一步的区间更新逻辑出了问题。在工程上我建议把二分核心逻辑封装成一个独立的函数然后写一个小的测试driver用随机数据自动验证。比如生成一个随机有序数组随机选target同时跑手写二分和标准库lower_bound结果不一致就打印现场数据。这个driver我几乎每个二分项目都会写不超过20行代码但能省下无数排查时间。5. 二分细节敲定的工程哲学与习惯养成回头再看“C二分细节敲定规则”这件事技术点其实就那么多区间定义、mid取整、循环不变量、边界返回值、check函数设计。但真正让一个人二分水平质变的不是记住某个模板而是养成一套敲定规则的思维习惯。我自己现在的习惯是拿到任何二分需求先花一分钟在纸上写清楚三件事。第一我要找的答案语义是什么是“第一个满足”还是“最后一个满足”还是“精确等于”。第二我准备维护什么区间是半开区间还是闭区间选定后整个过程不再切换。第三我的循环不变量是什么每次更新后答案还在不在区间内。这三件事敲定之后代码怎么写都是水到渠成的事。如果你现在还在被二分细节折磨建议别急着刷题先按这个思路把基础模板推演一遍再用几个经典题目验证相信我一旦捋顺这个流程二分会成为你最有把握的算法之一。最后再分享一个小技巧写二分时给变量起名字要带语义。别用l、r这种缩写用left、right条件允许的话用first_ok、first_bad这种带语义的名字。工程上的二分代码可读性往往比那点性能重要得多清晰的变量名会让边界讨论变得直观很多。这个习惯我坚持了好几年收益远超想象。