1. 为什么二分法值得在XTUOJ上单独开一个分类接触XTUOJ一段时间的人应该都有这种感觉题目刷到一定量之后真正卡住你的往往不是语法和数据结构而是那些“一眼看不出解法”的题。而在这类题目里二分法出现的频率极高。它不刻意考你多复杂的算法却总能在你毫无头绪的时候用最小的时间复杂度把问题干掉。在XTUOJ的题目分类里二分法基本可以自成一个板块从基础查找一路延伸到二分答案、实数二分、三分求极值层层递进值得单独拉出来系统性刷一遍。二分法核心的思想很简单在一个单调的序列里通过不断缩小搜索区间用O(log n)的代价找到目标值或最优解。这句话大家都会背但真正上了OJ能把二分写对、写稳、写得不出bug的人远没有想象中多。很多时候不是因为不懂原理而是因为边界处理、终止条件、整数溢出、精度控制这些细节没有形成一套稳定的处理习惯。XTUOJ上的二分题恰好覆盖了这些细节的几乎所有变体。这篇文章我打算按题型把XTUOJ上二分法相关的内容做一次梳理从原理到模板再到常见坑点把我在刷题过程中踩过的、别人也大概率会踩的坑一并讲清楚。不管你是刚接触算法竞赛的新手还是刷题到中期想系统整理二分法技巧的选手按这个分类走一遍应该能把二分法这块吃得更透。2. 先搞清楚二分法到底在“分”什么2.1 二分查找与二分答案的分界线很多人在XTUOJ上遇到二分题时第一反应是“这不就是在一个有序数组里找数字吗”然后套模板去写。但二分法在OJ题里其实分成两个完全不同的应用层次。第一个层次是二分查找。这个最直观给定一个单调有序的数组查找某个值是否存在或者找到第一个大于等于某个值的位置。这类问题有非常固定的模板写起来难度不大真正考的是你对边界条件的理解是否透彻。第二个层次是二分答案。这类题不问“某个值在不在数组里”而是问“满足某个条件的最小值/最大值是多少”。比如给定一段木材要切割成若干段等长的小段问能切出的最大长度是多少。这类问题没有现成的“数组”给你做二分你需要自己构建一个逻辑上的单调区间对答案的可能范围进行二分每次用check函数验证当前答案是否可行。在XTUOJ的题目分布中二分答案的占比往往高于二分查找因为它能和贪心、判定性DFS/BFS、前缀和甚至动态规划结合出题空间很大。很多选手在二分查找部分熟练之后一到二分答案就懵问题不在于二分本身而在于“如何把原问题转化为判定性问题”这一步没有打通。2.2 单调性二分法成立的唯一前提无论哪种二分底层逻辑只有一个单调性。区间左侧不满足条件右侧满足条件或者反过来。没有单调性就没有二分的用武之地。这里要特别提醒一个容易踩的误区单调性不一定体现在“数值大小”上更多时候体现在“条件是否成立”这个布尔值上。举个例子在木材切割问题中如果我们设切割长度为L对于每个L能切出的段数f(L)是单调递减的。当L很小时f(L)很大一定能满足题目要求的段数当L增大到一定程度f(L)会小于要求值条件就不成立了。条件从成立到不成立的转折点就是我们要找的答案。这种“条件单调性”才是二分答案题目的核心。理解这一点之后再去看XTUOJ上那些二分题你会发现自己能更快地识别题目类型如果题目求的是“最大值最小”“最小值最大”“满足条件的最短/最长长度”几乎可以立刻往二分答案方向想。3. XTUOJ二分法题型的分类地图3.1 基础二分查找精确查找与边界定位这部分对应的是最经典的二分查找场景在有序序列中查找目标值。XTUOJ上这类题的难度不高但很考验代码基本功尤其是边界处理。根据我自己的刷题体验这类题主要又分三种第一查找某个值是否存在。这个最简单标准模板直接写。第二查找第一个不小于目标值的位置也就是lower_bound。第三查找第一个大于目标值的位置也就是upper_bound。这两种边界定位用STL的lower_bound和upper_bound可以直接搞定但我强烈建议你在学习阶段自己手写一遍。因为很多二分答案题的内部判定逻辑本质上就是一个自定义的lower_bound你不会手写的话后面会非常被动。手写的时候要注意一个细节while循环的终止条件和mid的更新方式要配套。左闭右开区间和全闭区间的写法完全不同。我个人习惯用左闭右开区间原因后面在模板章节细说。3.2 二分答案最值优化的万能钥匙XTUOJ二分法题型里的重头戏我觉得就是二分答案。它的典型特征非常明显题目会问你最少多少天、最大多少长度、最短多少时间能完成某事。这类题的通用解法分三步第一步确定答案的上下界。下界通常是0或者输入的最小值上界通常是极大值或者输入的总和。第二步写一个check函数判断在当前答案mid下方案是否可行。第三步在上下界之间进行二分不断收敛答案。听起来很简单但真正把check函数写对才是难点。check函数的复杂度直接决定了整个算法的上限。比如在木材切割问题里check函数就是遍历每根木材累加能切出的段数复杂度是O(n)整个算法就是O(n log maxLen)。但如果题目改成二维平面上的覆盖问题check函数可能要跑一次BFS或者一次DP那就需要在二分框架之外再做一层设计。以我刷XTUOJ的经验二分答案题里面至少有三成是“看出来是二分答案但check写不出来”的情况。原因往往是题目里的约束条件之间互相牵扯没能抽象成独立的判定条件。这种情况没有捷径只能靠多做题积累转化思路。3.3 实数二分精度控制是唯一主题当题目答案不是整数时二分法就进入实数二分阶段。典型的如求解方程的根、求几何问题的最值、卡精度的高精度计算等。实数二分和整数二分最大的区别就是终止条件。整数二分用l r来判断实数二分则要看当前区间长度是否小于一个给定的精度eps。我见过很多新手在实数二分里直接写while (r - l 1e-3)然后被精度卡哭。正确的做法是eps通常取1e-6或者比题目要求精度小两个数量级。如果题目要求保留小数点后两位eps至少取1e-4最好取1e-6。另外实数二分里不存在“mid1”这种写法因为区间长度是连续的。在XTUOJ上做实数二分题建议养成统一的编码习惯设置一个足够小的eps循环固定次数而不是判断区间长度。比如直接for (int i 0; i 100; i)这样能完全避免死循环而且精度足够。这个方法在一些极端精度题目里非常好用。3.4 进阶玩法三分法与二分嵌套二分法在XTUOJ上的分类如果只停留在上面三块其实还不太完整。还有两类进阶题目比较有意思。三分法通常用于求解单峰函数的极值点比如给定一个函数求它在区间内的最大值或最小值。原理和二分法很像只不过每次把区间分成三份比较两个分割点处的函数值舍弃其中一段。在XTUOJ上这类题不多但一旦出现识别不出来会卡很久。二分嵌套则出现在一些比较复杂的题目里比如外层二分答案内层还需要二分查找某个值或者外层二分时间内层用贪心验证再或者三分套二分求极值。这种题的代码量不一定大但逻辑层次多非常考验思路清晰度。4. 实操环节从零写一个能AC的二分模板4.1 整数二分模板与边界推导这部分我直接给出一套参考模板。以查找第一个不小于target的位置为例使用左闭右开区间[l, r)代码如下int lower_bound(vectorint nums, int target) { int l 0, r nums.size(); // 左闭右开 while (l r) { int mid l (r - l) / 2; if (nums[mid] target) { l mid 1; } else { r mid; } } return l; }为什么这里用mid l (r - l) / 2而不是(l r) / 2原因只有一个防溢出。当l和r都接近int上限时直接相加会溢出成负数用减法计算能安全地得到同样结果。这个习惯一旦养成以后在任何需要二分的地方都能受益。另一个配套原则是当条件是nums[mid] target时说明mid位置严格小于目标值那么答案一定在mid右边所以要收缩左边界到mid 1反之如果nums[mid] targetmid可能是答案也可能答案在左边所以保留mid这个位置将右边界收缩到mid。整个过程不重不漏这就是“闭区间排除法”的核心。4.2 二分答案类问题的通用check函数框架二分答案题的代码框架其实比二分类简单因为二分部分千篇一律变数全在check函数。bool check(int x) { // 根据题目要求实现“x是否可行”的逻辑 // 如果可行返回true否则返回false } int main() { int l 0, r 1e9; // 根据题目调整上下界 while (l r) { int mid ((long long)l r 1) 1; // 用1防止死循环 if (check(mid)) { l mid; } else { r mid - 1; } } printf(%d\n, l); return 0; }注意这里mid的计算方式是(l r 1) 1也就是向上取整。为什么需要1如果使用向下取整在l和r相差1时mid等于l如果check(mid)为truel会保持不变导致死循环。这算是二分答案题里最容易踩的坑没有之一。很多XTUOJ上的题你能想通思路但就是死循环超时多半是这里出了问题。至于check函数怎么写完全取决于题目。我个人的习惯是先把check当成一个独立的子问题来处理优先保证它的正确性再回去优化性能。因为一旦check错了整个二分就是在正确的范围内找一个错误的答案完全白费。4.3 实数二分的两种写法对比实数二分我推荐固定循环次数的写法代码清晰且不容易出错double l 0, r 1e9; for (int i 0; i 100; i) { double mid (l r) / 2; if (calc(mid) target) { r mid; } else { l mid; } } printf(%.2f\n, l);100次循环对double来说已经远超所需精度且不会陷入死循环。另一种写法是while (r - l eps)代码看着更直观但eps的选取很讲究。如果eps设太大精度不够设太小循环次数暴增。相比之下固定循环次数反而是更稳妥的方案。4.4 实战演示木材切割问题拿一道很典型的二分答案题来演示完整过程。题目大意是这样的有n根原木长度分别为a[i]现在要把它们切割成m根长度相等的小段问能切出的最大长度是多少。第一步确定二分区间。最小可能长度是1最大可能是max(a[i])。第二步写check函数。给定长度mid遍历所有原木累加每根原木能切出的段数a[i] / mid判断总数是否大于等于m。第三步用上面提到向上取整的二分框架跑一遍。#include bits/stdc.h using namespace std; int n, m, a[100005]; bool check(int len) { long long cnt 0; for (int i 0; i n; i) { cnt a[i] / len; if (cnt m) return true; } return cnt m; } int main() { scanf(%d%d, n, m); int maxLen 0; for (int i 0; i n; i) { scanf(%d, a[i]); maxLen max(maxLen, a[i]); } int l 1, r maxLen, ans 0; while (l r) { int mid (l r) 1; if (check(mid)) { ans mid; l mid 1; } else { r mid - 1; } } printf(%d\n, ans); return 0; }这里我用了l r的写法而不是l r。两种写法都可以关键是整套流程要自洽。用l r时每次check通过就记录ans为mid再继续向右搜索这样避免最后输出时还要纠结l和r哪个才是答案。5. 常见问题与排查技巧实录5.1 死循环与无限循环这是二分法题里最常见的运行时错误。典型场景是程序在本地跑几个用例看着正常一提交就TLE。排查思路很固定先检查mid的更新方式是否能把区间真正缩小。如果区间长度是2l和r分别是5和6向下取整mid为5check(5)为true后lmid区间没有任何变化死循环就出现了。解决方案就一句话根据题意决定mid是否需要向上取整。凡是“可行就往右收缩”的二分建议都用(l r 1) 1凡是“可行就往左收缩”的可以用(l r) 1。这个规律我试过很多次基本能覆盖所有情况。5.2 边界条件与下标越界二分的边界错误往往表现为程序结果差1或者数组访问越界。典型场景是在查找类题目里如果目标值大于数组中所有元素lower_bound应该返回n但某些错误写法会返回n-1甚至越界访问。这里我建议统一使用左闭右开区间。因为在这个约定下循环条件l r指向了一个空区间时会自动退出最后返回的l天然就是“第一个大于等于目标值的位置”无需额外修正。而且r初始化为数组长度n而不是n-1也避免了许多边界判断。5.3 精度误差被判WA实数二分和浮点数输出很容易因为精度问题被判定为答案错误。这类题在XTUOJ上经常出现而且通常要求输出保留固定小数位比如两位小数。我踩过一次印象很深的坑一道题要求保留两位小数我eps设了1e-3结果交上去WA了好几次。后来把eps改成1e-7一次通过。原因很简单eps只能决定二分收敛的区间宽度但输出时四舍五入到两位小数要求的是绝对误差不超过0.01。如果二分区间本身比这个误差还大那中间任何值四舍五入后都可能差一位。一般来说eps比输出精度小两个数量级是最保守的安全做法。还有一个输出小技巧用printf(%.2f)输出时C的printf会做四舍五入但某些编译器或环境对于浮点数的舍入规则是“银行家舍入”即逢五不一定进位。为了避免这种玄学问题我通常会在输出前加上一个极小的偏移量比如printf(%.2f, ans 1e-8)。这个trick在精度卡得很死的题里能派上用场。5.4 二分答案check函数写错却查不出还有一种很难排查的情况二分框架没问题边界也对但答案始终差一点。问题几乎总是出在check函数里。这类错误的难点在于它不会让程序崩溃也不会超时而是给出一个看起来很有道理的错误答案。我的排查经验是先写一个暴力解法在小数据范围内和二分答案做对拍。这个习惯极其重要尤其在XTUOJ刷题时每道难一点的二分题我都会本地造一个暴力版本随机生成多组数据来对拍。一旦二分答案和暴力结果不一致直接输出mid和check结果逐层排查。这个方法虽然笨但有效能省下大量盲目提交试错的时间。5.5 二分查找与二分答案的混淆还有一种常见问题是看到题目里出现“查找”两个字就下意识套用二分查找模板结果发现题目并没有给你有序数组而是要求你求一个最优值。反过来有些题明明可以用二分查找做有人却硬去套二分答案框架。区分起来其实不难关键在于题目问的是“某个具体值在不在序列里”还是“满足条件的最值是多少”。前者通常是二分查找后者优先考虑二分答案。XTUOJ这类题目命名有时候有迷惑性刷的时候不要只看题目标题而是从问题本身出发判断。6. 我在XTUOJ刷二分题的一些实用小建议6.1 用模板拆解问题而不是背题很多人在刷题时会进入一个误区一个模板吃过天下。比如会用lower_bound就觉得自己会二分了遇到新题先往模板里套套不进去就卡住。我自己的经验是二分法作为一种思想它的生命力在于“判定性问题的转化能力”。每个题目真正值的不是那几行二分代码而是如何把原问题拆成一个单调的判定问题然后设计出高效的check函数。所以刷XTUOJ二分题时我一般会先写出伪代码把l、r、check的逻辑理清楚再动笔写正式代码。这个习惯让我少走了很多弯路。6.2 对拍补盲区前面提到过对拍这里再展开一下。对拍就是写一个暴力程序在数据范围很小的情况下用最朴素的方法求解然后随机生成测试数据比较暴力程序和二分程序的答案。当两者不一致时说明你的二分实现逻辑有bug。对拍步骤很简单准备三个程序sol.cpp你的二分答案版本、brute.cpp暴力版本、gen.cpp随机数据生成器。在命令行里写一个循环每次跑随机数据对比输出。这个过程自动化程度越高测的组数越多越能发现隐藏问题。我通常会跑到1万组以上确保边界情况都能覆盖到。6.3 认真读题注意数据范围XTUOJ的很多二分题有个特点不直接告诉你这题可以用二分而是通过大数据范围来暗示。比如n达到10^5甚至10^6如果不用O(n log n)或者更优的算法基本会超时。当你看到这种数据范围又发现题目带有明显的“求最值”含义时二分法就要第一时间进入你的候选算法清单。另外要注意整型溢出问题。当答案是int范围时mid (l r) / 2可能溢出这时候我会用mid l (r - l) / 2来写或者干脆把l、r定义成long long。别觉得小题小题就不注意真到关键时刻一个溢出能把你WA到怀疑人生。6.4 错题本存在的意义最后想提一个所有刷OJ的人都应该坚持的习惯错题记录。二分法的坑特别小小到你记住之后就不会再犯但如果不去记录三个月后再遇到很可能又踩一遍同样的坑。我一般会在本子上记三列题目名称、错误类型死循环/边界差1/精度WA/check错误、正确写法。这个习惯不仅对二分法有用对后面学其他算法也同样适用。XTUOJ上的题量不小光靠脑力记忆难免有盲区靠谱的错题本能帮你系统性地加固薄弱环节。刷题这东西最重要的不是刷了多少而是每个坑都只踩一次。6.5 保持代码风格统一很多人忽略代码风格对刷题效率的影响但我认为稳定的代码风格是减少bug的重要前提。拿二分来说如果你有时用左闭右开有时用全闭有时用while(lr)有时用while(lr)那出错的概率会成倍增加。与其每次临时想不如固定一套自己最顺手、最不容易错的写法所有题目都按这个套路来。我这套写法用了很久整数二分查找用左闭右开整数二分答案用l r、成功记录ans实数二分用固定循环100次。这套组合基本能覆盖XTUOJ上绝大部分二分题遇到特殊题再特殊化处理。心态也能更稳定。7. 二分法之外XTUOJ还能带给你什么顺着二分法这条线刷XTUOJ很多时候会不知不觉牵扯出其他算法。比如二分答案的check函数可能需要贪心可能需要对数组排序可能涉及前缀和甚至需要跑一个DFS来判断连通性。所以你刷二分的本质其实是在练习“如何设计判定函数”这一更高阶的算法思维。很多选手刷题有一个误区喜欢按算法标签刷二分就只刷二分图论就只刷图论导致真正遇到综合题时反应不过来。但XTUOJ上的题目编排其实很杂同一个知识点经常出现在不同的题型背景里。如果你能带着“二分作为一种工具服务于整个题目的解决过程”的意识去刷收获会比单纯按标签刷题大得多。说到底OJ刷题练的是思维模式不是记忆库。今天你能把二分的边界完全掌握明天学三分、学整体二分、学二分图相关的算法时你会发现很多思路都是相通的。从XTUOJ二分法这个分类开始打基础往后的路会越走越顺。