系列写到第六篇聊聊二分。算法竞赛里二分真的是一个特别有意思的存在它看起来简单到不行一行 while 循环加一个 mid 就能写出来但真正到了赛场上写错边界的人一抓一大把。更关键的是二分远不止“在数组里找一个数”这么单调它还能演化出二分答案、实数二分、带权二分、整体二分这些进阶玩法。这一篇我打算从最朴素的二分查找讲起一路拆到比较进阶的带权二分中间会穿插大量实操模板和踩坑记录希望能帮刚开始刷题的人把基础夯实也帮已经写过不少二分题的人把那几个容易出错的地方彻底理清。先记住一句话二分不是“在数据里找东西”而是“在一个单调的判定序列里找分界点”。理解这句话后面所有变种都是顺水推舟。1. 二分的前提单调性才是灵魂1.1 二分解决的是哪种问题很多人刚学二分的时候接触到的第一个例子就是有序数组里查找某个数。于是形成了一个刻板印象二分只能用在有序数组上。这是把二分理解窄了。严格来说二分能处理的问题是你有一个定义在某个区间上的判定函数函数值为 false 的区间和 true 的区间是连续且各自只有一段且你需要在其中找到那个从 false 变成 true 的分界点或者从 true 变成 false 的分界点。比如数组[1, 3, 5, 7, 9]要找第一个大于等于 6 的数。可以定义一个检查函数ok(x)表示这个数是否大于等于 6。数组前 4 个数都是 false最后一个是 true所以在“下标”这个区间上做二分即可。这里的“有序”只起到了保证ok单调连续的作用。所以在竞赛里判断一道题能不能二分不要只盯着“数据是不是有序”而要问三个问题答案是不是在一个连续整数/实数区间里能不能写一个 check 函数判断某个候选答案是否可行check 的结果是否随答案单调变化三个问题都是“是”就可以考虑二分。1.2 单调性为什么决定二分能不能用二分的本质是每一轮扔掉一半不可能产生答案的空间。为什么能做到这一点因为一旦 check(mid) 返回 true你就能断言整个左半边或者右半边都不可能再是答案。这个“能断言”的能力就是单调性给的。举个生活化的例子。假设你在烧水想知道“水温最低要多少度水才会沸腾”。定义ok(t)表示 t 度时水是否沸腾。温度从 20 度加到 100 度ok的结果一定是先是 false然后某一天突然变成 true之后一直是 true。这就是一个单调序列。于是你可以用二分快速找到那个临界温度而不用把每个温度都试一遍。如果水的沸点会忽高忽低今天 80 度开明天 95 度开那二分就没有用武之地只能扫一遍。在算法题里这种单调性经常藏在一些看起来很绕的条件里。比如“每段长度越长能切出的段数越少”“间隔越大能放下的牛越少”这些都是反比例式的单调关系同样能支持二分。只要你确认 check(mid) 的结果会随着 mid 变大从 true 变成 false或者从 false 变成 true就可以放心二。2. 整数二分的模板选择比想象中重要2.1 两套主流模板的取舍整数二分最烦人的问题就是边界你一不小心就死循环或者答案差一位。我在刷题早期也吃过不少亏后来发现与其自己临场推边界不如固定两套模板见题直接套。第一套叫“找最小值型”也就是找第一个满足条件的位置check(mid) 为 true 时答案在左边收缩右边界// 找第一个满足 check 的位置保证 check 单调递增 int l 0, r n; // 注意 r 可以是开区间 while (l r) { int mid (l r) 1; if (check(mid)) r mid; else l mid 1; } // 答案就是 l第二套叫“找最大值型”也就是找最后一个满足条件的位置check(mid) 为 true 时答案在右边收缩左边界// 找最后一个满足 check 的位置 int l 0, r n; // 一般是闭区间 while (l r) { int mid (l r 1) 1; // 注意这里加 1防死循环 if (check(mid)) l mid; else r mid - 1; } // 答案就是 l这两套模板的区别就一处当 check(mid) 成立时是把右边界收到 mid还是把左边界推到 mid。前者适用于“越往右越可能 true我们要第一个 true”的场景后者适用于“越往左越可能 true我们要最后一个 true”的场景。建议平时各自多写几道题让手形成肌肉记忆。到了赛场上哪怕是紧张的状态也不至于在边界上翻车。2.2 手写 lower_bound 与 upper_bound虽然 C 标准库提供了lower_bound和upper_bound但很多题目要求你手写尤其是一些 PTA 函数题会专门让你补全一个二分查找函数。这种题本质上考的就是上面两套模板的变体。// 手写 lower_bound返回第一个 x 的下标 int lower_bound(int a[], int n, int x) { int l 0, r n; // 右边界是开区间 while (l r) { int mid l (r - l) / 2; if (a[mid] x) r mid; else l mid 1; } return l; } // 手写 upper_bound返回第一个 x 的下标 int upper_bound(int a[], int n, int x) { int l 0, r n; while (l r) { int mid l (r - l) / 2; if (a[mid] x) r mid; else l mid 1; } return l; }lower_bound和upper_bound的差距就一个符号一个是 x就收缩右侧一个是 x才收缩右侧。这两个函数合起来可以快速算出某个值在有序数组里的出现次数upper_bound(a, n, x) - lower_bound(a, n, x)。这个技巧在统计频率、处理查询时非常常用。2.3 边界与死循环的根源整数二分最常见的 Bug 是死循环。死循环的根源其实很统一mid在某次循环里等于l导致区间没有真正缩小或者r的更新没有排除任何元素。为什么第二套模板里mid要写成(l r 1) 1而不是(l r) 1试想l 3, r 4的情况。如果mid (3 4) / 2 3然后 check(3) 成立执行l mid那么 l 还是 3r 还是 4循环永远出不去。但如果mid (3 4 1) / 2 4check(4) 成立时l 4区间收敛check(4) 不成立时r 3也收敛。这就是第二套模板要向上取整的原因。第一套模板则不存在这个问题。当区间只剩下两个元素时mid (l r) 1取的是靠左的那个。check 成立时r mid区间变窄不成立时l mid 1区间也变窄。所以它用向下取整就是安全的。还有个细节l r如果数值很大可能溢出int。虽然竞赛题里很多时候左右边界都在 1e9 以内但一旦数据范围到 1e18l r会直接超出 int。稳妥起见推荐写成l (r - l) / 2或l (r - l 1) / 2。这样既避免了溢出又保留了向上/向下取整的区别。3. 二分答案最优化到可行性的关键一跃3.1 什么时候能二分答案二分答案是把“求最优值”转化成“判断某个值是否可行”的经典技巧。它的适用范围非常聚焦题干里通常有明显的关键词比如“最大值最小”“最小值最大”“最大长度”“最小距离”等。这类题目如果直接求最优值很困难但给定一个候选答案判断它是否可行却很容易那八九不离十就是二分答案。打个比方。你要给一群朋友分蛋糕希望每个人拿到的蛋糕体积尽量大。直接算最大体积很复杂但如果你先定一个体积 x然后看所有蛋糕能不能切成若干块每块至少 x这个判断就简单多了。顺着这个思路把 x 从 0 开始往上二分找到最后一个能成功切出的 x就是答案。二分答案的核心功力在于写 check 函数。check 写得高效二分迭代个二三十次完全没问题check 写崩了整个算法直接废掉。所以每次写二分答案题我都会先单独写 check再套二分框架而不是混在一起写。3.2 实战切段数最大化来看一个非常典型的二分答案题。你有 n 根木棍长度分别为 a[i]现在要切出至少 m 段长度相同的小段求每一段的最大可能长度。如果直接想“最大长度是多少”不好想。但如果你定一个长度 len算一下每根木棍能贡献几段加起来看是否大于等于 m这件事就非常直接bool check(int len) { long long cnt 0; for (int i 0; i n; i) { cnt a[i] / len; } return cnt m; }注意如果 len 取 0除法会出问题所以二分左边界要从 1 开始。如果连长度为 1 都切不出 m 段那么答案就是 0这种情况可以等二分结束后特判一下也可以在一开始就排除。右边界一般取最长木棍的长度因为任何一段都不可能超过所有木棍里的最大值。主代码是典型的“找最大值型”int l 1, r maxLen; while (l r) { int mid (l r 1) / 2; if (check(mid)) l mid; else r mid - 1; } cout l endl;这道题刷明白以后像“切成 m 块巧克力”“木材加工”“跳石头”这类题都能很快上手因为它们本质上都是同一个套路二分一个长度check 里统计数量或次数最后判断是否满足题目限制。3.3 实战最大化最小值牛棚问题另一类高频二分答案是“最大化最小值”。最经典的题是牛棚问题有 n 个牛棚位置 x[i]你要把 c 头牛放进这些位置希望任意两头牛之间的最近距离尽可能大问这个最大最近距离是多少。这道题的 check 思路是贪心给定距离 d从最左边的牛棚开始放第一头牛然后往后扫只要当前牛棚和上一头牛之间的距离大于等于 d就在这个位置放下一头牛。最后统计能放下的牛的数量是否大于等于 c。bool check(int d) { int cnt 1; // 第一头牛放在 x[0] int last x[0]; for (int i 1; i n; i) { if (x[i] - last d) { cnt; last x[i]; } } return cnt c; }一看到“最近距离尽可能大”就知道要用“找最大值型”的模板。左边界可以是 1右边界取x[n-1] - x[0]二分开 log 次后输出答案。这道题是二分答案领域里非常经典的入门题因为它把“贪心验证 二分枚举”结合得特别典型。3.4 二分次数和复杂度估算二分答案最让人放心的就是时间复杂度非常可控。假设答案区间大小是S每次 check 的复杂度是O(f)那么总复杂度是O(f log S)。关于 log 的次数不需要精确算有一个速记方法如果答案范围在 1e9 左右二分大约 30 次如果答案范围在 1e18 左右大约 60 次。因为2^30约等于 1e92^60约等于 1e18。所以哪怕 check 的复杂度稍高一点只要不超过O(n)并带上常数整道题往往都能在时限内通过。不过有两个细节必须提醒。第一如果答案是long long那 check 里也尽量用long long涉及乘除法时尤其小心溢出。第二如果右边界非常大比如直接取1e18那么计算mid (l r) / 2时建议写成l (r - l) / 2防止l r在特殊编译器下出问题。4. 实数二分EPS 和循环次数怎么选4.1 推荐固定循环次数而不是只靠 EPS一旦答案从小数事情就变得有点麻烦。整数用除法不会产生误差浮点数会。常见写法有两种一种是while (r - l eps)另一种是for (int i 0; i 100; i)。我更推荐后者尤其是精度要求不明确的时候。原因是eps设小了r - l可能因为浮点精度永远减不到eps以下程序会死循环eps设大了答案精度不够输出会被判错。而固定循环次数比如 100 次每次区间缩小一半2^100已经远远超过任何浮点数能表达的范围最后区间会小到 double 的精度极限省心又稳定。double l 0, r 1e9; for (int i 0; i 100; i) { double mid (l r) / 2; if (check(mid)) l mid; else r mid; }注意这里l mid和r mid都不需要加减 1因为区间是实数mid 本身可能已经足够接近边界。循环结束后l和r的差距已经小到可以忽略取哪个都行。4.2 EPS 设置和输出精度对照如果需要用 EPS 写法怎么设置eps有一个常用经验如果题目要求输出保留 k 位小数那么eps至少要比1e-k再小两个数量级。比如要求保留 6 位小数eps设1e-8比较稳妥要求保留 9 位小数eps设1e-11甚至更小。输出要求推荐EPS推荐固定循环次数保留 3 位小数1e-560 次保留 6 位小数1e-880 次保留 9 位小数1e-11100 次保留 12 位小数1e-14120 次这里的逻辑是二分每迭代一次误差大约缩小一半。你想让误差从初始范围 1e9 缩小到 1e-8需要约30 27 57次迭代所以循环 60 次基本就到极限了。再多循环受 double 自身精度限制收益也不大但不会出错。4.3 浮点二分的一个小案例举一个简单的实数二分例子求x^3 - 5x 1 0的一个正实根。直接解方程很麻烦但你只需要判断 mid 处函数值是正还是负按单调区间收缩即可。double f(double x) { return x * x * x - 5 * x 1; } double l 0, r 3; for (int i 0; i 100; i) { double mid (l r) / 2; if (f(mid) 0) l mid; else r mid; }为什么f(mid) 0就往左收换成别的函数可能就要换方向因为你得事先判断函数在区间上是单调增还是单调减并确认你要找的是零点的哪一侧。这再次印证了二分的每一步都要想清楚“mid 的 check 结果和答案到底在哪一侧”。实数二分还有一个隐藏考点输出精度和浮点数比较。代码里尽量避免直接判断两个浮点数相等一般都会带上 EPS比如fabs(a - b) 1e-9才认为是相等。如果没这个习惯很容易在极端数据上栽跟头。5. 带权二分从入门到“不畏惧”5.1 带权二分解决什么约束问题带权二分是进阶内容了但近些年在各种高质量比赛里出镜率越来越高。它解决的一类问题是在普通的最优化问题上额外要求“恰好选 k 个/至多选 k 个/至少选 k 个”并且如果不加数量限制最优解的选择数量是变化的直接 DP 可能因为状态维度过高而超时。带权二分的思想很有意思它不直接限制选择的数量而是给每次选择加上一个“惩罚项”通过调节惩罚力度间接控制最优解里选择的数量。这个惩罚项通常是个常数 lambda选一次就扣一次。lambda 越小最优解越倾向于多选lambda 越大最优解越倾向于少选。于是通过二分 lambda可以让最优解恰好落在 k 附近。它还有一个更常见的名字叫 WQS 二分或者叫凸优化。为什么叫凸优化因为这类方法能成立的关键在于目标函数关于“选择的数量”呈现凸性即数量变化时最优收益的斜率单调。只有在这个前提下惩罚系数和选择数量之间才能形成单调对应关系。5.2 核心思想用一个惩罚系数控制选择数量我以一个简化模型来演示。假设你有一排位置每个位置有一个收益 w[i]要求选任意多个位置但相邻两个位置不能同时选。给定收益值问最多能得多少分。这是普通 DP。现在再加一个条件必须恰好选 k 个位置。如果你运气好k不大可以把“选了几个”作为状态维度变成二维 DP。但如果 n 是 10 万k 是 10 万二维 DP 直接爆炸。这时候就可以用带权二分。具体做法是先不管“恰好 k 个”的限制给每个被选的位置额外扣掉一个固定值 lambda也就是说选 i 这个位置的收益变成w[i] - lambda。然后跑一遍没有数量限制的 DP得到最优收益和此时最优方案里选择了多少个位置。显然lambda 越大扣得越多最优方案的选择数量就越少。于是你就在 lambda 上做二分找到一个临界值使得最优方案的选择数量落在 k 附近。最后算答案的时候把多扣的 lambda 加回去真实收益 带惩罚的最优收益 lambda * 实际选择数量。下面是一个阉割版的示例代码用来演示惩罚系数如何影响选择数量// dp[i]: 处理完前 i 个位置且第 i 个位置必选或必不选的最大收益简化版 // 重点看 lambda 如何影响 count细节按题目会变 const long long NEG -1e18; vectorlong long dp(n), cnt(n); for (int i 0; i n; i) { // 不选 i 时直接继承 dp[i-1] dp[i] dp[i - 1]; cnt[i] cnt[i - 1]; // 选 i 时第 i-1 个不能选所以从 dp[i-2] 转移 long long val (i 2 ? dp[i - 2] : 0) w[i] - lambda; if (val dp[i]) { dp[i] val; cnt[i] (i 2 ? cnt[i - 2] : 0) 1; } } // 最终 cnt[n-1] 就是当前 lambda 下最优方案的选择数量然后二分 lambda直到 cnt 逼近 k。但注意二分目标通常不是严格让 cnt 等于 k而是找到那个让 cnt 刚好超过 k 或者刚好不超过 k 的惩罚值。操作上我会在 check 里记录“在收益最大的前提下尽量选更多位置”还是“尽量选更少位置”取决于你最终想往哪个方向逼近。由于不同题目的转移不同这个细节需要自己微调但大方向就是上面这套。5.3 适用条件和易错点带权二分看起来很妙但它的前提非常苛刻目标函数关于选择数量必须是凸的。也就是说f(k)表示“恰好选 k 个时能获得的最大收益”那么随着 k 增大相邻两个收益之间的差值f(k) - f(k-1)必须单调不增或单调不减。如果不满足凸性你用惩罚项去调 lambda选择数量和收益之间就可能出现跳跃二分出来的结果完全不可信。怎么判断凸性一个粗糙但常用的方法如果f(k)的取值可以用一个“斜率递减的边际收益”来解释那大概率是凸的。比如每次多选一个带来的额外收益应该越来越少这就天然构成上凸或下凸结构。如果题目本身不满足带权二分就不能用只能老老实实做带数量限制的 DP。另外还有一些实操上的坑。第一收益和 lambda 都可能很大建议用long long甚至long double避免浮点数比较带来的误差。第二当多个方案收益相同但选择数量不同时你必须在 check 里规定一个统一偏好否则会让二分的单调性出现毛刺。第三最终答案的计算要格外小心如果你二分到的 lambda 对应的选择数量不完全等于 k通常要取靠近 k 的那个值并用公式把惩罚项还回去。带权二分不是一场比赛都能用到的常规武器但一旦用上它能解决很多看起来“不可做”的恰 k 限制问题。平时可以找几道经典题练手比如带权二分的最经典例题“种树”和“美食节”了解清楚以后别怕思路本身就是一种很漂亮的模型转换。6. 二分 Debug 与对拍技巧6.1 常见错误速查表二分题的 Bug 往往很难一眼发现因为错误不体现在语法上而是藏在逻辑边界里。我整理了一张高频错误表每次 AC 不了的时候对着查一遍效率会高很多症状可能原因解决思路程序死循环mid 取整方向错误或 check 为 true 时区间不缩小检查模板是否该用向上取整答案差 1初始边界没把答案包进区间确认 l 和 r 的取值是否覆盖全部可能答案check 成立但答案错误check 里用了全局变量或依赖的数据没排序单独测试 check不要混进二分里调试浮点输出不对EPS 过大或过小换用固定循环 100 次大样例 WA 但小样例 AC溢出检查 l r、乘法、除法是否越界统一用 long long6.2 高效的二分题调试流程面对一道 WA 的二分题我建议按下面这个顺序排查。第一步单独构造一个小数据手动模拟 check 函数看它是否符合你对“可行/不可行”的定义。很多二分题写错不是因为二分本身而是 check 压根写得有问题。第二步验证单调性。写一个临时循环把区间内一些值得注意的 mid 全部跑一遍输出 check 结果肉眼确认是不是“一段 false 一段 true”或者反过来。如果出现 true、false、true 这样的震荡问题不在二分模板而在 check 函数的定义或实现。第三步写暴力对拍。小范围数据可以直接枚举答案判断可行性再和二分算出来的结果比较。数据量不用大但要多生成几组随机数据专门找边界值、极端值去覆盖。只要有一组对不上就把那组数据单独拿出来打印 l、r、mid 和 check 的返回值很容易定位问题。第四步检查左右边界。有没有想过答案可能是 0可能是右边界本身二分结束后要不要特判这些细节虽然小但经常是 WA 的元凶。特别是二分答案题里如果题干允许“无法满足条件输出 0”一定要在边界上留出这个可能性。6.3 二分题写不顺时的心理建设最后说一点心理层面的经验。二分题写不出来或者反复 WA 的时候别急着改模板。先把题目里的“最优值”换成“给定一个值判断可不可行”让你自己说出这个转换。如果说不出来说明你对题目的单调性还没吃透硬套模板也没用。我个人的习惯是每道二分题动笔前先在草稿纸上写三行字答案区间是什么、check(mid) 怎么写、check 结果 true 时答案往哪边收。这三行写清楚了套模板基本就是手到擒来。做了几十道二分题以后你会发现这一类题反而不是考模板而是考你对“可行性”的定义能力。7. 再说说二分查找在 STL 和 PTA 里的用法有的读者可能在 PTA 上刷过函数题遇到让实现二分查找的题目。这种题目通常不允许直接用 STL要求你手写一个函数返回值是查找位置。别看题目简单它就是直接考察lower_bound的手写能力。所以前面 2.2 节那段代码建议熟练背诵不是背代码而是背里面的逻辑为什么r从n开始为什么a[mid] x时往左收。而在正式竞赛里能用 STL 就要用 STL。lower_bound和upper_bound底层是二分速度非常快还能直接配合vector、set等容器使用。手写模板主要用于理解原理实际生产环境优先调用标准库这是减少 Bug 的有效手段。顺便提一句二分查找在 STL 里还有一个容易记混的地方lower_bound返回的是“第一个不小于目标值的位置”upper_bound返回的是“第一个大于目标值的位置”。这两者在处理重复元素时差别很大。比如数组是[1, 2, 2, 2, 3]lower_bound找 2 返回位置 1upper_bound找 2 返回位置 4两者相减正好是 2 的个数 3。这个性质在做计数类题目时经常用到建议记牢。8. 实战里的最后几个细节二分相关的题目刷多了会发现真正的难点从来不是那几行二分代码而是 check 函数背后的贪心、DP、模拟甚至图论。只要你把 check 写对了二分框架只是锦上添花。所以我总是建议刷题的朋友看到“最大值最小”“最小值最大”“恰好 k 个”这种关键词先别急着套模板先在草稿纸上把可行性判定的问题想清楚再去写代码。另一个细节是数据范围。二分题的数据范围往往比普通暴力题大很多int经常不够用。一旦答案中间量可能超过 2e9就统一用long long不要抱着侥幸心理。我自己就曾经在一次模拟赛里因为 mid 计算时爆了int在一道二分答案题上白白丢了整道题的分数从那以后凡是二分题我第一眼就检查数据类型。如果你刚开始学二分我建议找下面几道经典题练手二分查找类可以找 PTA 上的手写函数题二分答案类可以刷“木材加工”“跳石头”“进击的奶牛”实数二分可以找一个单峰函数或单调函数的求零点题带权二分可以找“种树”和“美食节”。把这些刷透你的二分基础会非常扎实。我自己在竞赛中用二分的体会是它像一个杠杆用很少的代码量撬动了很大的复杂度优化。二分本身没有太多花哨的机制但它的思想能渗透到各种算法里和贪心、DP、网络流甚至数据结构结合。学二分最重要的不是记住模板而是养成“把最优性问题转化成可行性问题”的思维习惯。这种思维一旦养成遇到很多看似复杂的题目你都会下意识地开始思考这个答案能不能二分这种提问方式本身就是竞赛选手最核心的能力之一。
