二分与贪心算法精讲：边界处理、单调性与check函数设计指南

你有没有过这种经历明明知道“二分”这种算法题目也能看懂可一到写代码就卡在边界上要么死循环要么越界或者拿到一道“贪心”题感觉就是排序然后选一选结果样例过了提交上去一大片WA。二分与贪心专题在算法竞赛和面试里几乎算得上“基础中的基础坑里的高发区”。很多新手把它们当成背模板就能过关的题型但实际上这两个算法的核心并不是模板本身而是你如何理解“单调性”和“如何证明局部最优就是全局最优”。这篇东西算是带竞赛这些年积累下来的心得。我不会只列结论会把“为什么这样做”讲透从整数二分的边界哲学到贪心正确性的三种证明方法再到二分答案加贪心check的经典组合拳最后整理一份常见踩坑记录。无论是正在备考蓝桥杯、准备面试手撕算法还是刚学数据结构想夯实基础这篇文章都值得你花十分钟慢慢看每一段都可以直接抄作业。1. 二分不只是“折半查找”这个模板1.1 从“有序数组中找数”到“单调性质分段”先说二分。很多人第一次接触二分就是“在一个有序数组中查找某个值”于是形成了条件反射——提到二分就想到排序想到数组有序。这个理解不算错但它把二分的应用范围大大缩窄了。二分的本质不是“数组有序”而是存在一个判定条件使得问题的解空间可以被切分成“满足”和“不满足”两个连续区间。换句话说存在一个check函数f(x)当x从小到大变化时f(x)的结果要么是“一堆false之后全是true”要么是“一堆true之后全是false”。这种单调性才是二分真正依赖的底层属性。举个例子查字典。字典里的词条是按字母序排好的翻到中间一页比较目标词和当前词就能决定往左还是往右。这个过程中我们利用的就是“字母序”这个单调性质。如果没有这个性质比如去一个无序书架里找一本书二分就失效了。而在算法题里我们常常遇到的不是“找值”而是“找最优解”。这时候二分的对象往往是答案本身用check(mid)验证当前答案是否可行然后根据单调性收缩范围。这种套路叫二分答案后面详细展开。需要特别强调的是二分查找并不要求数组物理有序只需要满足判定条件关于下标或取值是单调的。比如旋转数组找最小值、峰值的左侧上升右侧下降都可以用二分因为它们都具备局部的单调分段性质。理解到这一层你才真正从“背模板”走向了“理解二分”。1.2 整数二分的边界哲学为什么你老是死循环整数二分是最容易出bug的地方。常见的错误包括死循环、左右边界错位、答案差一。要根治这个问题必须从mid的计算方式和边界收缩方式两个维度去分析。整数二分的核心麻烦在于当区间左右边界L和R相邻时mid(LR)//2会取到左边界L。如果此时你的收缩逻辑是Lmid也就是继续保留mid作为左边界区间就一直不缩小程序陷入死循环。反之如果你用的是Rmid那么区间会正常收缩不会死循环。所以实际操作中有两套模板可以固化一套适用于“找第一个满足条件的位置”一套适用于“找最后一个满足条件的位置”。第一套模板求最小满足条件的位置// 求最小的 x使得 check(x) 为 true // 假设 check 在 x 较小时为 false变大后为 true int l low, r high, ans -1; while (l r) { int mid l (r - l) / 2; if (check(mid)) { ans mid; r mid - 1; // 尝试更小的 } else { l mid 1; // mid 太小了往右找 } } // 最终 ans 就是答案如果没有满足条件的ans 保持 -1第二套模板求最大满足条件的位置// 求最大的 x使得 check(x) 为 true // 假设 check 在 x 较大时为 false int l low, r high, ans -1; while (l r) { int mid l (r - l) / 2; if (check(mid)) { ans mid; l mid 1; // 尝试更大的 } else { r mid - 1; // mid 太大了往左找 } }为什么用l (r - l) / 2而不是(l r) / 2因为当l和r都是接近int上限的大数时lr可能溢出用减法缩小的方式就可以规避这个问题。这不是玄学是实战中实实在在会踩的坑。还有一套很多人习惯用的左闭右开写法也可以但一旦混用就会崩。我的建议很直接选择一套你熟悉的模板每次只改check函数不要每次现推边界逻辑。比赛场上时间紧张边界推导的思维出错率远高于业务逻辑出错率。浮点二分相对简单。因为浮点数没有“相邻整数”的问题只需要控制精度。常见写法是循环固定次数比如100次或者判断区间长度小于eps时终止推荐前者因为eps太小可能导致死循环太大又精度不够固定次数则稳定可靠。比如答案范围是0到1e9二分100次后区间长度为1e9/2^100远小于任何合理精度要求。1.3 二分答案把“最优问题”变成“判定问题”的开关如果说二分查找是“在有序空间里找目标”那么二分答案就是“在答案的取值范围内猜答案然后用check函数验证”。为什么这个问题能这么处理因为很多最优问题的答案和可行性之间存在单调关系。先看一个经典场景要把一列数分成若干段要求每段和的最大值尽可能小。直接求最优分段很难但如果你给定一个上限x问“能否用不超过k段使得每段和都不超过x”这个判定问题就容易多了——从左往右累加超过x就另起一段最后统计段数是否超过k。这个判定问题的结果关于x是单调的x越大越容易满足也就是不需要太多段。既然单调就可以二分x找到最小的满足条件的x那就是最优解。这类题目一般有比较明显的特征词“最大值最小”“最小值最大”“最多不超过”“至少需要多少”。看到这些第一反应就应该是二分答案加一个判定函数。二分答案具体分几步走第一步确定答案范围。题目没给范围时可以用一个极大值作为上界比如1e18或者通过推公式确认有范围时直接用L和R。 第二步编写check(x)函数。这一步是重中之重它只需要回答“满足或不满足”不需要给出具体方案。 第三步套用整数二分模板输出答案。需要注意check函数的复杂度决定了整个算法的复杂度。如果check是O(N)的那么二分的总复杂度就是O(N log R)其中R是答案范围。在数据范围比较大的题目里这也是可以接受的因为log级别增长很慢。为什么很多人遇到二分答案会想不到我觉得关键是没有建立“答案也是可枚举对象”的意识。一上来就想着怎么直接算出最优解反而走进了死胡同。二分的优势在于它把“求最优”这个很抽象的问题降维成了“猜答案并验证”这种高容错的流程思维的负担一下子减轻很多。2. 贪心局部最优与全局最优之间的距离2.1 贪心思想的适用边界为什么有些题“一看就贪”却不对与二分相比贪心没有统一的模板它更像是一种决策原则在每一步都做出当前看起来最优的选择并希望这些局部最优累积成全局最优。听起来很简单但悲剧恰恰藏在“希望”两个字里。一个经典反例大家都熟悉背包问题。如果每个物品可以拆分也就是分数背包那贪心按单位价值排序就能做但如果是0-1背包每个物品只能整体取走贪心按单位价值排序就会出错也许一个又大又重的物品刚好填满剩余容量从而比一堆小物品更优。差别就在“能否拆分”决定了子问题是否独立、局部决策是否影响后续空间。所以贪心的适用需要满足两个性质其一是贪心选择性质即每一步的最优选择一定包含在某个全局最优解里其二是最优子结构性质即做出贪心选择后剩下的子问题仍然可以独立求解。这两个性质看似抽象但在实践中你的脑海里需要有一个默认流程先凭直觉提出一个贪心策略然后立刻尝试证明或寻找反例。证明不出来的策略十有八九有问题。很多新手会犯一个毛病看到“最小最大”“最优方案”就觉得是贪心样例过了就开始欢呼。这是很不好的习惯。贪心题的最优解往往是“反直觉”的——比如区间调度按开始时间排序就不如按结束时间排序部分背包按重量排序也不如按单位价值排序。你要做的是先找出排序依据再验证这个依据是否能经得起证明的检验。2.2 正确性证明三件套交换论证、反证法、归纳法贪心必须证明否则心里没底。我平时最常用的有三种证明手段熟练之后你会发现它们不仅能验证思路还能反过来帮你建造正确的贪心策略。第一种交换论证法。它的思路是任取一个最优解如果最优解里存在两个元素和贪心解不一致尝试交换它们的位置。如果交换后解不会变差那么贪心解至少和最优解一样好因此贪心解就是最优解。这个方法特别适合排序类的贪心问题。举个例子活动选择问题每个活动有开始时间和结束时间安排尽量多的不重叠活动。贪心策略是按照结束时间从小到大排序依次选择不与已选活动冲突的活动。证明时假设最优解的第一个活动不是当前最早结束的活动我们把它替换成最早结束的活动因为前者结束时间更晚替换后剩下的空间只会更多松弛性妥妥的。于是“选最早结束”的活动总是安全的。第二种反证法。假设贪心解不是最优解那么存在一个更优解。然后分析这个更优解与贪心解的第一个分歧点发现这个分歧会导致矛盾于是推翻假设。区间选点问题和活动选择问题都能用这种手法证明形式上比交换论证更直接。第三种数学归纳法。适用于那种贪心决策会不断缩小子问题的题型。证明第一步的贪心选择保留下来的解仍然是最优解然后归纳证明后续每一步同样如此。哈夫曼编码的贪心证明用的就是归纳法思路每次合并权值最小的两棵树保证最终带权路径长度最小。我个人的建议是写代码之前至少用一分钟说明白“为什么我的贪心策略是对的”。说清楚了再写代码也不容易返工。如果解释不了那就老老实实考虑用动态规划或者搜索暴力替代——贪心一旦错了debug的难度比动态规划还高。2.3 高频贪心模型一览区间、排序、哈夫曼合并贪心题目虽多但模型其实是高度结构化的做多了你会发现基本都是那几个套路在反复变形。先看区间类问题。区间选点要求用最少的点覆盖所有区间做法是右端点排序然后每次贪心地选最靠右的点能覆盖更多区间区间调度要求选尽可能多的不重叠区间做法是按结束时间排序每次挑最早结束的。这类题目的共同点是排序维度决定成败选错排序维度就是全军覆没。再看排序类问题。比如“国王游戏”“皇后游戏”这类题通常给出两个指标比如左值和右值要求排列顺序使得某个量的最大值最小。这类题的核心是发现一个二元交换的判别式然后按这个判别式排序。例如如果交换相邻两个元素后最大值不会变差那么交换前的排列就更优。推导出排序规则后排序本身只是顺带的事真正难的是那个贪心比较规律。还有哈夫曼模型。合并果子、石子合并的最相邻版本每次合并权值最小的两堆总代价最小。这类问题的证明不复杂用扩展的交换论证即可但它的变形很多比如限定只能合并相邻的两堆那就变成了区间DP问题贪心不再适用。贪心模型的本质其实是一种直觉训练你积累的模型越多看到新题时就越容易在几秒内想到排序依据。我的经验是每做完一道贪心题都要回头总结“这道题的贪心依据是什么按结束时间按比值按区间右端点”积累十几种模型之后新题基本都能用旧模型去套。3. 二分 贪心最经典的组合拳3.1 为什么二分答案常常需要配一个贪心check单独讲完二分和贪心下面把它们放在一起看。在很多“最大值最小化”或“最小值最大化”的题目里存在一个很妙的组合思路二分答案负责猜测最终阈值贪心负责在给定阈值下进行可行性检验。为什么二分的check函数经常用贪心实现因为当目标值被限定以后判断“是否可行”往往比“求最优解”简单很多而且这种判定问题常常带有自然的前向扫描特征从左到右扫一遍能留就留不能留就分——这正是贪心的用武之地。我举一个特别经典的例子跳石头。题目大意是在一条长度L的河道上有若干块石头起点和终点固定最多移走M块石头求移走石头后相邻石头之间最短跳跃距离的最大值。直接求最短距离最大值非常绕但如果我们换一个表述给定一个最小距离x问“至少要移走多少块石头才能让任意相邻石头的距离都不小于x”。这个判定问题就非常适合贪心扫描从当前石头开始依次检查下一块如果下一块与当前石头距离小于x那它就必须被移走否则保留它并把它当作新的当前石头。统计一下要被移走的石头总数如果小于等于M说明这个x是可行的。因为x越大需要移走的石头只会越多所以可行性关于x是单调的。于是我们可以二分x每次运行贪心check找到最大的可行x。下面是完整的参考代码核心思路就是把“最优问题”转成“判定问题”#include bits/stdc.h using namespace std; typedef long long ll; const int MAXN 50000 5; int d[MAXN], L, N, M; bool check(int x) { int cnt 0; // 需要移走的石头数量 int last 0; // 上一次停留的位置0表示起点 for (int i 1; i N; i) { if (d[i] - last x) { cnt; // 这块石头必须移走 } else { last d[i]; // 保留这块石头 } } if (L - last x) cnt; // 最后一段到终点也要验证 return cnt M; } int main() { scanf(%d%d%d, L, N, M); for (int i 1; i N; i) scanf(%d, d[i]); int left 0, right L, ans 0; while (left right) { int mid (left right) / 2; if (check(mid)) { ans mid; left mid 1; } else { right mid - 1; } } printf(%d\n, ans); return 0; }这个题有个细节最后一段“从最后一块石头到终点”也要检查是否小于x如果小于x说明这块石头也留不得计数要加一。新手特别容易漏掉这个边界导致答案偏大。同样的套路可以套到很多题上面。比如“放置奶牛”问题有N个牛棚位于一条线上要在其中选择C个位置放奶牛问最近的两头奶牛之间的距离最大能是多少。check(x)的实现就是贪心地在牛棚之间留出至少x的距离统计能放下几头然后二分x。你看是不是一模一样的骨架3.2 完整推导从题目特征到check函数设计的四步法面对一道疑似二分答案加贪心的题目我一般按四步走可以极大降低思维难度。第一步判读特征。看到“每组和的最大值最小”“任意两点之间的最小值最大”“至少需要多少运力”这类表述直接进入二分答案赛道。第二步确定单调性。判断一下当答案x变大的时候判定条件更容易满足还是更难满足确认方向后才能决定是求最小值还是最大值。如果x越大越容易满足说明check返回true的区间在右边要求最小可行x如果x越大越难满足那check返回true的区间在左边要求最大可行x。第三步推check函数。目标不是“求出最优解”而是“回答一个yes/no问题”。沿着数组或者空间从左往右一次遍历遇到不符合当前阈值的就进行下一段或移除统计需要修改的次数。注意边界处理起点、终点、最后一个元素都要纳入检验范围。第四步套模板。按之前的整数二分模板写出主流程输出ans。这四步法尤其适合校招笔试和竞赛里的进阶题。你不需要证明太多理论只要能说明单调性就可以放心地套二分答案至于贪心check的正确性只要你的贪心逻辑能用手动小样例验证并且有“每一步不得不这样做”的直觉支撑基本就不会翻车。4. 掉坑记录与调试方法4.1 二分常见报错死循环、越界和精度陷阱二分代码很少但出bug的时候特别耗时间因为代码结构看起来完全没问题为什么会死循环呢我整理了一份高频问题速查表建议收藏。现象可能原因解决方案程序卡死疑似死循环mid偏向一边且边界更新使用了lmid用midl(r-l)/2并保证l和r更新后至少缩小一个单位数组访问越界二分求出答案后直接作为下标使用没有判断范围输出ans前确认ans在合法范围内或用ans初始化为-1答案总是差1check函数的判定方向反了检查单调性方向确认是“越大约容易”还是“越大约难”浮点二分死循环直接用while(high-low eps)且eps过小改成循环固定100次稳定可靠大整数溢出(lr)/2在极端数据下溢出改用l(r-l)/2死循环这个问题我多说两句。调试时可以在代码里临时加一个计数器超过1e6次自动跳出打印l和r的中间值。你会看到l和r在相邻位置反复横跳这时候基本可以断定是边界更新问题。避免越界的一个小技巧如果check函数里要访问mid1或者mid-1先把mid本身限定在中间范围不要使用l0、rN这种天然容易越界的边界组合把左边界设为0、右边界设为N访问完再检查下标是否落在0到N之间。还有一个隐藏坑当mid非常大时check函数里可能会有乘法或累加导致long long溢出。我见过不少选手在二分check里算乘积时忘记转long long直接爆了。记得在check函数里把变量全部声明为long long尤其是累加统计的场景。4.2 贪心“看起来对”却翻车反例收集与自测技巧贪心题最怕的不是没思路而是思路错误却没有发现。我总结了几条实战中验证贪心正确性的做法。第一小数据暴力对拍。数据范围小的时候用DFS或DP暴力找出全局最优解然后和贪心结果对比。随机生成几千组小数据如果有一组匹配不上说明贪心策略有问题赶紧回去修。这是检验贪心的黄金标准比自己人脑硬想高效得多。第二寻找“反直觉”的排序维度。当你有一个排序方案时试着问自己换一种排序维度会怎样比如如果按左端点排序能过右端点排序会不会更好我见过太多人因为样例排序方式不敏感导致实际提交时WA。建议在一个题上多试两种排序看最终结果是否一致。第三警惕“只看眼前不看剩余”的决策。检查贪心策略是否遗漏了全局约束。比如0-1背包按单位价值排序会错就是因为忽略了剩余容量的整体约束。如果你发现决策会导致剩余资源被浪费这个贪心大概率是错的。第四注意并列情况下的次序。排序时如果主关键字相同次关键字是否要排序比如区间选点右端点相同的情况下左端点大的区间应该优先选因为更窄的区间在前面的点已经被覆盖时更容易满足。这种细节通常不会写进题解但实际调试的时候能让人很头疼。4.3 训练路线与最后的几点心得如果你正准备系统性攻克二分与贪心专题我建议的训练顺序是这样的先把整数二分的两个模板和浮点二分的固定次数循环练熟用几道经典题找感觉比如“有序数组查找”“查找第一个大于等于目标值的位置”“在排序数组中查找元素的第一个和最后一个位置”。然后进入二分答案阶段做“跳石头”“放置奶牛”“切绳子”“网线主管”这一类经典题。这个阶段的核心就是锻炼“从题目信息识别单调性”的能力。再到贪心阶段按模型分类刷题区间调度、区间选点、区间覆盖、合并果子、国王游戏、任务调度。每一类做完后都逼自己写一段证明文字不用发出去写在备忘录里就行。最后做二分加贪心的混合题。这一阶段你会发现综合题并不难难的是能不能反应过来“这题是二分答案”一旦识别出来check函数往往几分钟就能写完。我个人在实际操作中的体会是这两个算法正确率的提升靠的是“训练时的不放过”。如果你看到一道二分题边界条件写错了不要只改对就完事把当时的错误原因记下来——是方向反了还是mid更新写错是越界了还是check漏掉了边界数据下一次遇到类似错误直接翻笔记本比现场画边界快得多。还有一点想分享的小技巧写二分时先写check函数再套模板。因为check是整个二分的灵魂模板只是外壳。很多人上来就写主循环想着一会儿再补check结果写着写着就把边界弄混了。反过来先把check函数验证无误再套模板主循环基本不会出问题。这些内容说到这儿其实已经覆盖了二分与贪心专题中最容易让人卡住的部分。跳出书本的例题在真实赛题里你还会遇到花式变体但只要抓住“单调性判断”和“局部决策可验证”这两个底层逻辑再怎么变都不怕。训练时多花时间在证明和自测上比赛时自然就能省下大量试错的时间。