带过不少打算法竞赛的学弟也面过不少候选人发现一个很有意思的现象二分查找算法和贪心算法这两个看似最基础的专题恰恰是区分“背过模板”和“真会算法”的分水岭。很多人能背出二分模板却看不懂题目里隐藏的单调性能说出“贪心就是每次选最优”却写不出严格证明结果在“局部最优”的坑里反复翻滚。这个“二分与贪心专题”要解决的正是从识别到落地的完整链路什么时候用二分、二分答案的本质是什么、贪心怎么选决策、怎么证明贪心正确、哪些经典题可以拿来反复练手。无论你是刚开始刷题的大学生、准备校招笔试的求职者还是工作中想写出高效代码的工程师这套专题都值得从头到尾捋一遍。我不会只给你模板而是把每个判断背后的原因讲透让你之后再遇到“求最大值的最小值”“按某种规则排序后取最优”“带限制的最优化”这类题目时能条件反射般找到解题方向。1. 专题概览二分与贪心为什么总被放在一起1.1 两个算法的底层思维模式先聊二分。二分的核心前提只有一个单调性。在一个有序或者满足某种单调性质的搜索空间里我们通过不断缩半把线性扫描变成对数级别的查找。它真正牛的用法不是“在数组里找一个数”而是把“求最优值”的难题转换成“判断某个值是否可行”的简单题——这就是“二分答案”。贪心的核心前提也只有一个全局最优可以由一系列局部最优决策推出也就是贪心选择性质和最优子结构。贪心算法每次只做一个选择看起来简单但难点在于证明这个“每次都选眼前最好的”真的能得到全局最优。这两个算法放在一起讲是因为它们在思维上互为补充二分依赖的是“答案的单调性”贪心依赖的是“决策的局部最优性”而很多复杂题目恰恰需要二者配合比如用二分答案枚举一个阈值再用贪心判断这个阈值能不能做到。理解这种配合关系比单独背任何一个模板都重要。1.2 用一个生活化案例建立直观认识想象你在评估一个项目方案需要在限定预算内完成任务。二分答案的思路是先猜一个总预算然后检查“用这个预算能不能完成”能就降低预算再试不能就提高预算——最终卡在能完成的最小预算上。贪心的思路则是每一步都选择“当前性价比最高”的那项支出直到预算耗尽——然后证明这样做不会比任何其他选择差。生活里我们其实经常混用这两种策略。比如出门旅行规划路线如果目标是“在一天内尽量多打卡景点”你大概率会对总时间做二分试探设定一个游览时长看路线能否覆盖而选定路线后具体去哪个景点往往是按“距离相近排队短”的贪心原则边走边选。算法题就是把这些日常直觉严格化、形式化的过程。1.3 专题学习路线建议我建议的学习顺序是先掌握整数二分的两个模板和边界处理再用“二分答案判定函数”打穿最优化问题然后进入贪心专题重点练排序策略的选择和正确性证明最后做几道二分贪心的复合题体会两者如何协同。别急着刷题量。二分专题里真正值得反复做的是那几道“求最大化最小值”“最小化最大值”的题因为它们的判定函数经常要借助贪心来实现;贪心专题里优先吃透区间调度、哈夫曼编码、任务安排这几个经典模型。这些模型不是孤立的它们会反复出现在后续的网络流、动态规划优化、机器学习特征选择等进阶内容里。2. 二分查找从模板到内化2.1 整数二分的两种边界写法整数二分最容易踩坑的就是边界和死循环。这里我直接给出经过大量题目验证的两个模板分别对应“找左边界”和“找右边界”两种场景。核心区别在于取中点的方向以及 l、r 的更新规则。模板一求第一个满足条件的位置左边界int l 0, r n - 1; while (l r) { int mid (l r) 1; // 向下取整 if (check(mid)) r mid; // mid 满足条件答案在左边或就是 mid else l mid 1; // mid 不满足答案必然在右边 }模板二求最后一个满足条件的位置右边界int l 0, r n - 1; while (l r) { int mid (l r 1) 1; // 向上取整 if (check(mid)) l mid; // mid 满足条件答案在右边或就是 mid else r mid - 1; // mid 不满足答案必然在左边 }两个模板的差异不是随便定的。模板一里更新l mid 1时中点向下取整没问题因为 mid 已经被排除模板二里更新r mid - 1时如果不把取整方向调成向上当l和r相邻比如 l3, r4时mid (34)1 3如果 check(3) 成立执行l 3区间不缩反而不变直接死循环。加上1让mid4才能保证每次循环区间长度严格减半。这个细节我见过太多次翻车了。很多人在基础题上没问题一换到“求右边界”的题就卡死循环原因就是把取整方向搞反了。建议把两个模板都背下来并且在做题前先想清楚我要找的是满足条件的哪一个端点是第一个还是最后一个这决定了模板的选择。2.2 PTA 和力扣里的函数式写法如果你在 PTA拼题A这类平台上做过“二分查找”题会发现它们的函数签名通常是这样的int search(int arr[], int len, int target) { int l 0, r len - 1; while (l r) { int mid l (r - l) / 2; // 防止 lr 溢出 if (arr[mid] target) return mid; else if (arr[mid] target) l mid 1; else r mid - 1; } return -1; }注意这里用了l r的闭合区间写法和前面两个模板的l r写法不同。闭合区间写法适合“确认 target 一定存在”的简单查找但遇到“查找第一个大于等于 target 的位置”这种变体时还是建议回到前面l r的模板框架。还有一个易错点mid (l r) 1在l r超过 int 范围时会溢出。虽然竞赛题里 n 通常不会大到溢出但力扣和面试场景里数组长度可能接近 2^31用l (r - l) / 2这种形式更安全。面试官其实很看重这个细节它是区分“只会背模板”和“真正理解原理”的试金石。2.3 实数二分精度控制与迭代次数实数二分不需要担心死循环因为区间确实会不断缩小但需要担心的是精度没控制好导致答案错误。常见的做法有两种固定迭代次数或者用while (r - l eps)。double l 0, r 1e9; for (int i 0; i 100; i) { // 100 次迭代足够把区间缩到极小 double mid (l r) / 2; if (check(mid)) l mid; else r mid; } // 或者 while (r - l 1e-7) { double mid (l r) / 2; if (check(mid)) l mid; else r mid; }我个人的经验是优先使用固定迭代次数法。理由有两个第一它不受 eps 设得过小导致死循环的影响第二100 次迭代已经能把 1e9 规模的区间缩小到 1e-18 以下精度远远足够。用eps的方式则要注意题目要求的输出精度一般要求保留 3 位小数就设千万分之一的 eps 即可不要太小否则浮点误差会让程序无法及时停止。3. 二分答案把“求最值”变成“判可行”3.1 二分答案的适用场景判断二分查找和二分答案最大的区别在于前者搜索的“数组”是真实存在的后者搜索的是“答案的值域”。二分答案适用于具有以下特征的问题题目要“求最大值”或“求最小值”但这个最大值/最小值反过来有一个单调的判定性质——即“如果 x 可行那么所有比 x 更宽松的值都可行如果 x 不可行那么所有比 x 更严格的值都不可行”。具体来说出现过下面这些表述的题目都值得往二分答案方向想求“最小的最大距离”最大化最小值求“最大的最小花费”最小化最大值“能否在限定时间内完成”“能否用不超过 X 的资源做到”要求输出一个数值解而直接求解困难、判定容易一个经典例子是“分巧克力”给定若干块尺寸不同的长方形巧克力要切出至少 K 块边长相等的小正方形求最大可能的边长。直接求这个最大边长不容易但判定函数很好写给定边长 x计算能切出多少块看是否大于等于 K。因为边长越大能切出的块数越少单调性成立直接二分边长即可。3.2 判定函数的设计常常是贪心扫描二分答案的灵魂不在二分本身而在判定函数 check(x)。判定函数设计好题目就完成了一大半设计不好二分框架再熟练也是白搭。判定函数最常见的实现方式就是贪心扫描。比如上面切巧克力就遍历每块巧克力累加能切出的块数碰到不够 K 就提前退出。再比如“伐木工”问题给定树高和需要的木材总长求最小锯片高度判定函数就是扫描所有树把高于 x 的部分累加起来看是否足够。这类贪心扫描往往没有复杂的决策就是一个循环内做累加和比较写起来很快。我建议比赛时先把 check 函数单独写成一个函数不要和二分逻辑混在一起。这样既能统一调试也方便测试不同的判定策略。如果 check 函数本身需要排序、维护堆等复杂逻辑也不要慌把它当成一个“给定的输入够不够用”的子问题独立解决。3.3 分治解法与二分解法、带权二分的来龙去脉在动态规划优化里你们可能听过“四边形不等式优化”有一类叫“分治解法”另一类叫“二分解法”。这里的“二分”和我们前面说的“二分答案”不太一样它指的是在区间 DP 中如果决策点随着位置移动而单调右移我们可以用二分/分治来快速寻找最优转移点。具体场景是这样的某些 DP 方程为dp[i][j] min(dp[i][k] dp[k1][j] cost)当代价函数满足四边形不等式时最优分割点k随i、j单调变化。于是有两种加速方式一种是用分治整体求解每一层枚举区间时利用决策单调性缩小枚举范围另一种是在枚举每组 (i,j) 时用二分找到使代价最小的 k。两者本质都在利用单调性只是一个偏分治框架、一个偏二分查找。带权二分也叫 WQS 二分、凸优化又是一个不同的进阶玩法当 DP 方程有一个维度是“限制选择次数 k”而答案关于 k 是凸函数时我们给每次选择附加一个权值然后二分这个权值使得不加限制的 DP 恰好能用满 k 次选择反解出真实答案。听着绕但它是“二分答案思维”在动态规划优化里的深度延伸。初学者不建议一上来就啃这个但学到高级阶段思路会比较顺。4. 贪心算法局部最优如何导向全局最优4.1 贪心成立的两个核心条件贪心算法在竞赛里常被误解为“猜一个策略然后试一试”。实际上贪心的正确性有明确标准通常两个条件缺一不可贪心选择性质每一步做出的局部最优选择最终能导出全局最优解即不用考虑未来的选择来修正当前决策。最优子结构一个问题的全局最优解包含其子问题的最优解。举例来说找零钱问题里如果硬币面额是 1、5、10、25用贪心总能得到最少硬币数但换成面额 1、3、4贪心就失效了找 6 元时贪心会选 411共 3 枚而最优是 33 两枚。为什么因为 3 和 4 之间不满足贪心选择性质。这个例子虽然简单却是理解贪心边界最好的入门素材。在《算法导论》贪心算法那一章里作者用“活动选择问题”一步步展示了如何从动态规划转移到贪心先写出递归定义证明剩余问题的最优解就是选择最早结束的活动后对剩余活动继续做贪心最终把 O(n^2) 的 DP 化成了 O(n) 的贪心扫描。这个推导过程值得亲手走一遍它是理解“为什么贪心是对的”最快的路径。4.2 三大经典模型区间、调度、哈夫曼区间调度问题是贪心入门的第一课给一堆区间选尽量多的互不重叠区间。排序策略是“按结束时间从小到大”选完一个后跳过所有与它重叠的区间。为什么按结束时间排不按开始时间或区间长度排因为更早结束的区间给后续留下的空间更大这正满足贪心选择性质。学习时建议亲手试想起来按开始时间排序为什么不行比如区间 [1,10]、[2,3]、[4,5]按结束排序能选两个按开始排序会先选 [1,10] 只剩一个。调度问题稍微进阶一点若干任务有执行时间和截止时间求最大能完成的任务数。常见策略是按截止时间排序依次处理如果当前总用时超过截止时间就丢弃已选任务中执行时间最长的那一个通常用最大堆维护。这个方法粗看反直觉因为它不是简单地“能完成就保留”而是“总超时了就丢掉最重的包袱”保证已选任务数量最多且总用时尽量短。分析它的正确性要用交换论证是很好的进阶练习题。哈夫曼编码是典型的树形贪心每次从集合中取出权值最小的两个节点合并直到剩一个根。核心证明是“权值最小的两个节点一定位于最深层且互为兄弟”如果它们不在最深层交换后总代价不会变大。这个交换论证非常漂亮理解了它你就抓到了贪心证明的通法。4.3 贪心排序策略的通用推导法遇到新题怎么设计贪心策略我的经验是先假设“两个相邻元素 a 和 b 应该按什么顺序”然后算交换前后这个局部代价的变化得到一个“比较函数”。这就是经典的排序条件推导法。举个例子若干任务有“耗时 t 和分数惩罚 c”要安排执行顺序使总惩罚最小常见策略是比较c1 * t2与c2 * t1的大小决定谁先谁后。不要凭直觉猜直接算如果先做 a 再做 b 和先做 b 再做 a 的总惩罚差多少然后整理成一个可比较的表达式最后用这个表达式作为排序的 comparator。用这种方法推导出来的排序规则基本上不会错。还有一种常见工具是反证法假设最优解中相邻两个元素没有按“我们设计的规则”相邻说明交换后会更优矛盾。能写出这一小段证明不只让自己放心面试时讲出来也是绝对的加分项。5. 专题实战经典题目的完整拆解5.1 分巧克力二分答案贪心判定的组合拳样例背景有 n 块长方形巧克力尺寸不一。要切出边长均为整数的正方形总共至少 K 块求正方形最大边长。拆解思路确定二分的东西边长 x。明确单调性x 越大能切出的块数越少。编写 check(x)遍历每块巧克力累加(w[i] / x) * (h[i] / x)如果总数 K 返回 true。这里面容易被忽略的是每块长方形能切出的块数公式要写成整数除法不要先算出总面积再除 x^2。因为切出来的块数受两个维度整除限制总面积除法会放大块数导致答案偏大。这就是典型的“贪心扫描整数细节”混合坑。5.2 活动安排贪心经典的第一道题题意是给定若干活动的开始时间 s[i] 和结束时间 e[i]每个时间点只能参加一个活动求最多能参加几个活动。拆解思路按结束时间从小到大排序。维护当前最后结束时间 last。遍历每个活动如果活动开始时间 last就参加并更新 last 为该活动结束时间。这个题的正确性证明值得写一遍假设贪心选择了第一个活动 a而某个最优解第一个选择了 b因为 a 的结束时间不晚于 b所以可以把最优解中的 b 替换成 a剩余活动的选择空间不会变小新解仍然是最优。重复这个替换贪心解就和某个最优解完全一致。有了这个证明你才算真正掌握了这道题。5.3 最大化最小值消防站选址类问题这类问题在二分答案里最经典。比如在一条直线上有 n 个村庄要建 m 个消防站让每个村庄到最近消防站的距离最大值最小。拆解思路二分答案假设最大距离是 x。判定从第一个村庄开始如果当前村庄到最近消防站距离超过 x就必须在距离它不超过 x 的位置放一个消防站实际做题时常简化为在它位置放一个站然后跳过所有被覆盖的村庄数一数需要多少个消防站是否 m。二分左端点往小调右端点往大调最终逼近最小可行 x。这道题的价值在于它展示了二分贪心的结合如何把“最优化问题”降维成一个“可行性扫描问题”。判定函数里的贪心是“及时建站、尽量覆盖”判定完成后二分去逼近答案。很多复杂的竞赛题比如牛舍问题、网络基站覆盖都是这个模型的变体。6. 常见问题与调试技巧实录6.1 二分死循环的三种典型症状死循环只发生在整数二分里实数二分几乎不会死循环。最常见的三种情况模板选错该求右边界却用了左边界模板l mid时中点没有向上取整。循环条件写错用l r却在中途把r mid不排除 mid导致区间无法缩半。check 函数写错导致结果不单调二分依赖单调性如果 check 本身不满足单调条件二分框架会进入反复横跳。排查方法在小数据上单步调试打印每次 mid 和 check(mid) 的结果。如果发现两次输出同样的 mid说明更新规则有问题。l mid系列一定要配mid (l r 1) 1这是硬规矩。6.2 实数二分的精度陷阱实数二分常见错误不是死循环而是输出精度不够或者长时间不退出。我建议固定迭代 80~100 次省心且稳定如果一定要用 eps 判断注意 eps 不要小于1e-8否则在极端数据下可能因为浮点误差永远不满足退出条件。另外要留意输出格式题目要求保留 3 位小数建议输出前加一个微小的数比如 1e-7来补偿浮点截断误差否则 2.345 可能输出成 2.344。这是实战里很常见的小坑但特别容易让人交冤枉罚时。6.3 贪心排序条件写错时的排查方法贪心排序条件是错题重灾区。现象是小数据全对大数据答案偏小或偏大。排查步骤把 comparator 写成一个独立函数用 20 个以内的随机元素打印排序结果人工检查是否满足直觉。用暴力解法全排列或状态压缩对小数据求真实最优解和自己贪心结果对拍。交换论证重新写一遍如果两个相邻元素交换后代价不变或更差说明排序规则逻辑成立否则就是比较函数缺失了某个关键变量。我特别推荐“暴力对拍”这个方法它不只是调试工具更是验证贪心直觉的试金石。很多我一开始觉得显然正确的贪心策略都是在对拍时被小数据打脸的。6.4 通用调试技巧造数据与对数器无论是二分还是贪心我最推荐的调试流程是写一个数据生成器随机生成小规模数据n 10。写一个正确但较慢的算法比如 DP 或枚举作为核对基准。用自己的贪心/二分答案实现跑同一批数据对比输出。这一步能在 5 分钟内定位 80% 的错误。千万不要对着大数据盲猜数据一大你根本不知道错在哪一步。对数器是算法竞赛玩家最核心的调试武器刷这个专题之前建议先花半小时搭一套自己顺手的对拍脚本。7. 刷题顺序与个人体会如果说要给这个专题做一份提升练手清单我的推荐顺序是入门套力扣第 35 题二分查找、力扣第 704 题、活动安排区间调度问题。进阶套分巧克力、伐木工、最大化最小值、带惩罚的调度问题。拔高套带权二分相关的 DP 优化题、四边形不等式优化配合二分的区间 DP。刷题数量不用贪多但每一道都要走完“识别模型→写出框架→手写证明→对拍验证”这四个环节。特别是证明那一步别跳它决定你以后能不能处理没见过的新题。我个人在这些年的刷题和教学中最大的体会是二分和贪心表面上是“模板题”实际是“思维题”。二分的难点永远不在 mid 怎么取而在你能否发现答案具有单调性贪心的难点永远不在怎么选决策而在你能否证明每一步的选择不会在未来付出更大代价。这两件事都需要大量刻意练习但它们带来的回报也是巨大的——几乎所有进阶算法从图论最短路到网络流从 DP 优化到机器学习中的特征选择底层都残留着二分或贪心的影子。我至今还记得自己第一次靠交换论证说服自己“按结束时间排序选活动”时那种开窍的感觉。这道题之后再遇到的贪心题我不再靠猜而是先假设、再交换、最后得出结论。希望这篇专题笔记也能帮你找到同样的感觉。
二分与贪心算法：从背模板到真正掌握核心思维
带过不少打算法竞赛的学弟也面过不少候选人发现一个很有意思的现象二分查找算法和贪心算法这两个看似最基础的专题恰恰是区分“背过模板”和“真会算法”的分水岭。很多人能背出二分模板却看不懂题目里隐藏的单调性能说出“贪心就是每次选最优”却写不出严格证明结果在“局部最优”的坑里反复翻滚。这个“二分与贪心专题”要解决的正是从识别到落地的完整链路什么时候用二分、二分答案的本质是什么、贪心怎么选决策、怎么证明贪心正确、哪些经典题可以拿来反复练手。无论你是刚开始刷题的大学生、准备校招笔试的求职者还是工作中想写出高效代码的工程师这套专题都值得从头到尾捋一遍。我不会只给你模板而是把每个判断背后的原因讲透让你之后再遇到“求最大值的最小值”“按某种规则排序后取最优”“带限制的最优化”这类题目时能条件反射般找到解题方向。1. 专题概览二分与贪心为什么总被放在一起1.1 两个算法的底层思维模式先聊二分。二分的核心前提只有一个单调性。在一个有序或者满足某种单调性质的搜索空间里我们通过不断缩半把线性扫描变成对数级别的查找。它真正牛的用法不是“在数组里找一个数”而是把“求最优值”的难题转换成“判断某个值是否可行”的简单题——这就是“二分答案”。贪心的核心前提也只有一个全局最优可以由一系列局部最优决策推出也就是贪心选择性质和最优子结构。贪心算法每次只做一个选择看起来简单但难点在于证明这个“每次都选眼前最好的”真的能得到全局最优。这两个算法放在一起讲是因为它们在思维上互为补充二分依赖的是“答案的单调性”贪心依赖的是“决策的局部最优性”而很多复杂题目恰恰需要二者配合比如用二分答案枚举一个阈值再用贪心判断这个阈值能不能做到。理解这种配合关系比单独背任何一个模板都重要。1.2 用一个生活化案例建立直观认识想象你在评估一个项目方案需要在限定预算内完成任务。二分答案的思路是先猜一个总预算然后检查“用这个预算能不能完成”能就降低预算再试不能就提高预算——最终卡在能完成的最小预算上。贪心的思路则是每一步都选择“当前性价比最高”的那项支出直到预算耗尽——然后证明这样做不会比任何其他选择差。生活里我们其实经常混用这两种策略。比如出门旅行规划路线如果目标是“在一天内尽量多打卡景点”你大概率会对总时间做二分试探设定一个游览时长看路线能否覆盖而选定路线后具体去哪个景点往往是按“距离相近排队短”的贪心原则边走边选。算法题就是把这些日常直觉严格化、形式化的过程。1.3 专题学习路线建议我建议的学习顺序是先掌握整数二分的两个模板和边界处理再用“二分答案判定函数”打穿最优化问题然后进入贪心专题重点练排序策略的选择和正确性证明最后做几道二分贪心的复合题体会两者如何协同。别急着刷题量。二分专题里真正值得反复做的是那几道“求最大化最小值”“最小化最大值”的题因为它们的判定函数经常要借助贪心来实现;贪心专题里优先吃透区间调度、哈夫曼编码、任务安排这几个经典模型。这些模型不是孤立的它们会反复出现在后续的网络流、动态规划优化、机器学习特征选择等进阶内容里。2. 二分查找从模板到内化2.1 整数二分的两种边界写法整数二分最容易踩坑的就是边界和死循环。这里我直接给出经过大量题目验证的两个模板分别对应“找左边界”和“找右边界”两种场景。核心区别在于取中点的方向以及 l、r 的更新规则。模板一求第一个满足条件的位置左边界int l 0, r n - 1; while (l r) { int mid (l r) 1; // 向下取整 if (check(mid)) r mid; // mid 满足条件答案在左边或就是 mid else l mid 1; // mid 不满足答案必然在右边 }模板二求最后一个满足条件的位置右边界int l 0, r n - 1; while (l r) { int mid (l r 1) 1; // 向上取整 if (check(mid)) l mid; // mid 满足条件答案在右边或就是 mid else r mid - 1; // mid 不满足答案必然在左边 }两个模板的差异不是随便定的。模板一里更新l mid 1时中点向下取整没问题因为 mid 已经被排除模板二里更新r mid - 1时如果不把取整方向调成向上当l和r相邻比如 l3, r4时mid (34)1 3如果 check(3) 成立执行l 3区间不缩反而不变直接死循环。加上1让mid4才能保证每次循环区间长度严格减半。这个细节我见过太多次翻车了。很多人在基础题上没问题一换到“求右边界”的题就卡死循环原因就是把取整方向搞反了。建议把两个模板都背下来并且在做题前先想清楚我要找的是满足条件的哪一个端点是第一个还是最后一个这决定了模板的选择。2.2 PTA 和力扣里的函数式写法如果你在 PTA拼题A这类平台上做过“二分查找”题会发现它们的函数签名通常是这样的int search(int arr[], int len, int target) { int l 0, r len - 1; while (l r) { int mid l (r - l) / 2; // 防止 lr 溢出 if (arr[mid] target) return mid; else if (arr[mid] target) l mid 1; else r mid - 1; } return -1; }注意这里用了l r的闭合区间写法和前面两个模板的l r写法不同。闭合区间写法适合“确认 target 一定存在”的简单查找但遇到“查找第一个大于等于 target 的位置”这种变体时还是建议回到前面l r的模板框架。还有一个易错点mid (l r) 1在l r超过 int 范围时会溢出。虽然竞赛题里 n 通常不会大到溢出但力扣和面试场景里数组长度可能接近 2^31用l (r - l) / 2这种形式更安全。面试官其实很看重这个细节它是区分“只会背模板”和“真正理解原理”的试金石。2.3 实数二分精度控制与迭代次数实数二分不需要担心死循环因为区间确实会不断缩小但需要担心的是精度没控制好导致答案错误。常见的做法有两种固定迭代次数或者用while (r - l eps)。double l 0, r 1e9; for (int i 0; i 100; i) { // 100 次迭代足够把区间缩到极小 double mid (l r) / 2; if (check(mid)) l mid; else r mid; } // 或者 while (r - l 1e-7) { double mid (l r) / 2; if (check(mid)) l mid; else r mid; }我个人的经验是优先使用固定迭代次数法。理由有两个第一它不受 eps 设得过小导致死循环的影响第二100 次迭代已经能把 1e9 规模的区间缩小到 1e-18 以下精度远远足够。用eps的方式则要注意题目要求的输出精度一般要求保留 3 位小数就设千万分之一的 eps 即可不要太小否则浮点误差会让程序无法及时停止。3. 二分答案把“求最值”变成“判可行”3.1 二分答案的适用场景判断二分查找和二分答案最大的区别在于前者搜索的“数组”是真实存在的后者搜索的是“答案的值域”。二分答案适用于具有以下特征的问题题目要“求最大值”或“求最小值”但这个最大值/最小值反过来有一个单调的判定性质——即“如果 x 可行那么所有比 x 更宽松的值都可行如果 x 不可行那么所有比 x 更严格的值都不可行”。具体来说出现过下面这些表述的题目都值得往二分答案方向想求“最小的最大距离”最大化最小值求“最大的最小花费”最小化最大值“能否在限定时间内完成”“能否用不超过 X 的资源做到”要求输出一个数值解而直接求解困难、判定容易一个经典例子是“分巧克力”给定若干块尺寸不同的长方形巧克力要切出至少 K 块边长相等的小正方形求最大可能的边长。直接求这个最大边长不容易但判定函数很好写给定边长 x计算能切出多少块看是否大于等于 K。因为边长越大能切出的块数越少单调性成立直接二分边长即可。3.2 判定函数的设计常常是贪心扫描二分答案的灵魂不在二分本身而在判定函数 check(x)。判定函数设计好题目就完成了一大半设计不好二分框架再熟练也是白搭。判定函数最常见的实现方式就是贪心扫描。比如上面切巧克力就遍历每块巧克力累加能切出的块数碰到不够 K 就提前退出。再比如“伐木工”问题给定树高和需要的木材总长求最小锯片高度判定函数就是扫描所有树把高于 x 的部分累加起来看是否足够。这类贪心扫描往往没有复杂的决策就是一个循环内做累加和比较写起来很快。我建议比赛时先把 check 函数单独写成一个函数不要和二分逻辑混在一起。这样既能统一调试也方便测试不同的判定策略。如果 check 函数本身需要排序、维护堆等复杂逻辑也不要慌把它当成一个“给定的输入够不够用”的子问题独立解决。3.3 分治解法与二分解法、带权二分的来龙去脉在动态规划优化里你们可能听过“四边形不等式优化”有一类叫“分治解法”另一类叫“二分解法”。这里的“二分”和我们前面说的“二分答案”不太一样它指的是在区间 DP 中如果决策点随着位置移动而单调右移我们可以用二分/分治来快速寻找最优转移点。具体场景是这样的某些 DP 方程为dp[i][j] min(dp[i][k] dp[k1][j] cost)当代价函数满足四边形不等式时最优分割点k随i、j单调变化。于是有两种加速方式一种是用分治整体求解每一层枚举区间时利用决策单调性缩小枚举范围另一种是在枚举每组 (i,j) 时用二分找到使代价最小的 k。两者本质都在利用单调性只是一个偏分治框架、一个偏二分查找。带权二分也叫 WQS 二分、凸优化又是一个不同的进阶玩法当 DP 方程有一个维度是“限制选择次数 k”而答案关于 k 是凸函数时我们给每次选择附加一个权值然后二分这个权值使得不加限制的 DP 恰好能用满 k 次选择反解出真实答案。听着绕但它是“二分答案思维”在动态规划优化里的深度延伸。初学者不建议一上来就啃这个但学到高级阶段思路会比较顺。4. 贪心算法局部最优如何导向全局最优4.1 贪心成立的两个核心条件贪心算法在竞赛里常被误解为“猜一个策略然后试一试”。实际上贪心的正确性有明确标准通常两个条件缺一不可贪心选择性质每一步做出的局部最优选择最终能导出全局最优解即不用考虑未来的选择来修正当前决策。最优子结构一个问题的全局最优解包含其子问题的最优解。举例来说找零钱问题里如果硬币面额是 1、5、10、25用贪心总能得到最少硬币数但换成面额 1、3、4贪心就失效了找 6 元时贪心会选 411共 3 枚而最优是 33 两枚。为什么因为 3 和 4 之间不满足贪心选择性质。这个例子虽然简单却是理解贪心边界最好的入门素材。在《算法导论》贪心算法那一章里作者用“活动选择问题”一步步展示了如何从动态规划转移到贪心先写出递归定义证明剩余问题的最优解就是选择最早结束的活动后对剩余活动继续做贪心最终把 O(n^2) 的 DP 化成了 O(n) 的贪心扫描。这个推导过程值得亲手走一遍它是理解“为什么贪心是对的”最快的路径。4.2 三大经典模型区间、调度、哈夫曼区间调度问题是贪心入门的第一课给一堆区间选尽量多的互不重叠区间。排序策略是“按结束时间从小到大”选完一个后跳过所有与它重叠的区间。为什么按结束时间排不按开始时间或区间长度排因为更早结束的区间给后续留下的空间更大这正满足贪心选择性质。学习时建议亲手试想起来按开始时间排序为什么不行比如区间 [1,10]、[2,3]、[4,5]按结束排序能选两个按开始排序会先选 [1,10] 只剩一个。调度问题稍微进阶一点若干任务有执行时间和截止时间求最大能完成的任务数。常见策略是按截止时间排序依次处理如果当前总用时超过截止时间就丢弃已选任务中执行时间最长的那一个通常用最大堆维护。这个方法粗看反直觉因为它不是简单地“能完成就保留”而是“总超时了就丢掉最重的包袱”保证已选任务数量最多且总用时尽量短。分析它的正确性要用交换论证是很好的进阶练习题。哈夫曼编码是典型的树形贪心每次从集合中取出权值最小的两个节点合并直到剩一个根。核心证明是“权值最小的两个节点一定位于最深层且互为兄弟”如果它们不在最深层交换后总代价不会变大。这个交换论证非常漂亮理解了它你就抓到了贪心证明的通法。4.3 贪心排序策略的通用推导法遇到新题怎么设计贪心策略我的经验是先假设“两个相邻元素 a 和 b 应该按什么顺序”然后算交换前后这个局部代价的变化得到一个“比较函数”。这就是经典的排序条件推导法。举个例子若干任务有“耗时 t 和分数惩罚 c”要安排执行顺序使总惩罚最小常见策略是比较c1 * t2与c2 * t1的大小决定谁先谁后。不要凭直觉猜直接算如果先做 a 再做 b 和先做 b 再做 a 的总惩罚差多少然后整理成一个可比较的表达式最后用这个表达式作为排序的 comparator。用这种方法推导出来的排序规则基本上不会错。还有一种常见工具是反证法假设最优解中相邻两个元素没有按“我们设计的规则”相邻说明交换后会更优矛盾。能写出这一小段证明不只让自己放心面试时讲出来也是绝对的加分项。5. 专题实战经典题目的完整拆解5.1 分巧克力二分答案贪心判定的组合拳样例背景有 n 块长方形巧克力尺寸不一。要切出边长均为整数的正方形总共至少 K 块求正方形最大边长。拆解思路确定二分的东西边长 x。明确单调性x 越大能切出的块数越少。编写 check(x)遍历每块巧克力累加(w[i] / x) * (h[i] / x)如果总数 K 返回 true。这里面容易被忽略的是每块长方形能切出的块数公式要写成整数除法不要先算出总面积再除 x^2。因为切出来的块数受两个维度整除限制总面积除法会放大块数导致答案偏大。这就是典型的“贪心扫描整数细节”混合坑。5.2 活动安排贪心经典的第一道题题意是给定若干活动的开始时间 s[i] 和结束时间 e[i]每个时间点只能参加一个活动求最多能参加几个活动。拆解思路按结束时间从小到大排序。维护当前最后结束时间 last。遍历每个活动如果活动开始时间 last就参加并更新 last 为该活动结束时间。这个题的正确性证明值得写一遍假设贪心选择了第一个活动 a而某个最优解第一个选择了 b因为 a 的结束时间不晚于 b所以可以把最优解中的 b 替换成 a剩余活动的选择空间不会变小新解仍然是最优。重复这个替换贪心解就和某个最优解完全一致。有了这个证明你才算真正掌握了这道题。5.3 最大化最小值消防站选址类问题这类问题在二分答案里最经典。比如在一条直线上有 n 个村庄要建 m 个消防站让每个村庄到最近消防站的距离最大值最小。拆解思路二分答案假设最大距离是 x。判定从第一个村庄开始如果当前村庄到最近消防站距离超过 x就必须在距离它不超过 x 的位置放一个消防站实际做题时常简化为在它位置放一个站然后跳过所有被覆盖的村庄数一数需要多少个消防站是否 m。二分左端点往小调右端点往大调最终逼近最小可行 x。这道题的价值在于它展示了二分贪心的结合如何把“最优化问题”降维成一个“可行性扫描问题”。判定函数里的贪心是“及时建站、尽量覆盖”判定完成后二分去逼近答案。很多复杂的竞赛题比如牛舍问题、网络基站覆盖都是这个模型的变体。6. 常见问题与调试技巧实录6.1 二分死循环的三种典型症状死循环只发生在整数二分里实数二分几乎不会死循环。最常见的三种情况模板选错该求右边界却用了左边界模板l mid时中点没有向上取整。循环条件写错用l r却在中途把r mid不排除 mid导致区间无法缩半。check 函数写错导致结果不单调二分依赖单调性如果 check 本身不满足单调条件二分框架会进入反复横跳。排查方法在小数据上单步调试打印每次 mid 和 check(mid) 的结果。如果发现两次输出同样的 mid说明更新规则有问题。l mid系列一定要配mid (l r 1) 1这是硬规矩。6.2 实数二分的精度陷阱实数二分常见错误不是死循环而是输出精度不够或者长时间不退出。我建议固定迭代 80~100 次省心且稳定如果一定要用 eps 判断注意 eps 不要小于1e-8否则在极端数据下可能因为浮点误差永远不满足退出条件。另外要留意输出格式题目要求保留 3 位小数建议输出前加一个微小的数比如 1e-7来补偿浮点截断误差否则 2.345 可能输出成 2.344。这是实战里很常见的小坑但特别容易让人交冤枉罚时。6.3 贪心排序条件写错时的排查方法贪心排序条件是错题重灾区。现象是小数据全对大数据答案偏小或偏大。排查步骤把 comparator 写成一个独立函数用 20 个以内的随机元素打印排序结果人工检查是否满足直觉。用暴力解法全排列或状态压缩对小数据求真实最优解和自己贪心结果对拍。交换论证重新写一遍如果两个相邻元素交换后代价不变或更差说明排序规则逻辑成立否则就是比较函数缺失了某个关键变量。我特别推荐“暴力对拍”这个方法它不只是调试工具更是验证贪心直觉的试金石。很多我一开始觉得显然正确的贪心策略都是在对拍时被小数据打脸的。6.4 通用调试技巧造数据与对数器无论是二分还是贪心我最推荐的调试流程是写一个数据生成器随机生成小规模数据n 10。写一个正确但较慢的算法比如 DP 或枚举作为核对基准。用自己的贪心/二分答案实现跑同一批数据对比输出。这一步能在 5 分钟内定位 80% 的错误。千万不要对着大数据盲猜数据一大你根本不知道错在哪一步。对数器是算法竞赛玩家最核心的调试武器刷这个专题之前建议先花半小时搭一套自己顺手的对拍脚本。7. 刷题顺序与个人体会如果说要给这个专题做一份提升练手清单我的推荐顺序是入门套力扣第 35 题二分查找、力扣第 704 题、活动安排区间调度问题。进阶套分巧克力、伐木工、最大化最小值、带惩罚的调度问题。拔高套带权二分相关的 DP 优化题、四边形不等式优化配合二分的区间 DP。刷题数量不用贪多但每一道都要走完“识别模型→写出框架→手写证明→对拍验证”这四个环节。特别是证明那一步别跳它决定你以后能不能处理没见过的新题。我个人在这些年的刷题和教学中最大的体会是二分和贪心表面上是“模板题”实际是“思维题”。二分的难点永远不在 mid 怎么取而在你能否发现答案具有单调性贪心的难点永远不在怎么选决策而在你能否证明每一步的选择不会在未来付出更大代价。这两件事都需要大量刻意练习但它们带来的回报也是巨大的——几乎所有进阶算法从图论最短路到网络流从 DP 优化到机器学习中的特征选择底层都残留着二分或贪心的影子。我至今还记得自己第一次靠交换论证说服自己“按结束时间排序选活动”时那种开窍的感觉。这道题之后再遇到的贪心题我不再靠猜而是先假设、再交换、最后得出结论。希望这篇专题笔记也能帮你找到同样的感觉。
