“贪心策略”和“二分查找”名字听起来一个像“差不多先生”一个像“绝对严谨的尺子”但我在实际刷题和带新人时发现这两者不仅不是对立的反而经常是黄金搭档。很多人单学贪心时觉得太简单每步选最优而已嘛单学二分时又觉得太繁琐边界到底是左闭右闭还是左闭右开背了忘、忘了背。可一旦把这两个东西合在一起用“二分答案 贪心验证”去解那些“最小化最大值”“最大化最小值”的题目整个思路就会顺畅很多。这篇文章不需要你有多深的算法基础我会从贪心到底什么时候成立讲起再拆二分查找里最容易翻车的边界问题最后用一个通用套路把两者缝合起来。无论你是在准备考试、刷 OJ 题库还是工作中偶尔要写一点搜索和优化逻辑这篇文章都值得你花十几分钟读完并且可以直接照着抄代码。1. “贪心”这个译名害了不少人它真不是“顺手拿个最优”先聊贪心。贪心策略的官方说法是每一步都做出在当前看来最优的选择并且一旦做出选择就不再回头。这个定义本身没什么问题但“贪心”这个译名带了一种“拿最大好处”的暗示导致很多人以为贪心就是“每次挑数值最大的那个”。1.1 一个反例胜过十句警告我们先看找零钱问题假设有面值 1、7、10 的硬币需要通过找零组成总额 14。如果按“贪心”即每次都拿面值最大且不超过剩余金额的硬币第一步拿 10剩余 4第二步只能拿 1剩余 3第三步拿 1剩余 2第四步拿 1剩余 1第五步拿 1完成一共用了 5 枚硬币。但最优解明明只需要 2 枚7 7。这就是贪心失效的典型现场。一个策略只有在“局部最优组合起来就是全局最优”的问题上才成立而这个性质在硬币面额组合不当时并不成立。那为什么现实中的人民币、美元硬币 1、5、10、20、25、50 这类面额下贪心找零往往又是对的因为这些面额满足一种特殊的“倍数箱体结构”局部拿大面额不会抢掉后面组合的可能性。这说明一个很重要的事贪心不是万能公式它是“特定结构问题”的特解。你做题时如果上来就默认贪心先要问一句这个问题有没有反例。1.2 贪心成立的两个底层性质判断一道题能不能用贪心最朴素的依据是检查两个性质第一是贪心选择性质通过每次的局部最优选择至少能构造出某一个全局最优解。也就是说当前这一步选“看起来最好”的那个不会把最优解堵死。第二是最优子结构性质问题的最优解包含子问题的最优解。做完当前的选择后剩余部分的最优解和当前选择拼接起来仍然是完整问题的最优解。这两条缺一不可。贪心选择性质保证了“选这个不亏”最优子结构保证了“剩下的还有救”。举个例子经典的活动安排问题有一堆会议每个会议有开始时间和结束时间会议室只有一个问最多能安排多少场不冲突的会议。正确贪心策略是按照结束时间从小到大排序每次都选“能选且最早结束”的会议。为什么因为选了最早结束的会议给后面留出的时间一定不会比选别的会议更少这就是贪心选择性质。而选完一场之后剩下可供安排的会议集合又是一个同样的子问题剩下安排的场数加上当前这场就是最优——这就是最优子结构。两个性质都满足贪心才稳。1.3 怎么证明贪心正确三种常用姿势光靠感觉“这个策略很自然”是不够的OJ 不会因为你觉得自然就让你过题。证明贪心通常有三个方向数学归纳法先证明第一步的贪心选择能导向最优解然后假设前 k 步贪心是最优的再证明第 k1 步贪心选择仍然是最优的。交换论证法假设存在一个最优解它某一步没有采用贪心方案。证明把这个最优解里的对应元素“交换”成贪心方案后结果不会变差甚至更好。反复交换就能得到“存在一个最优解完全等于贪心解”。反证法假设贪心解不是最优推导出矛盾。我实际写题时一般先在纸上用交换论证。活动安排就是典型任意最优解中第一场会议如果不是最早结束的那场就把它换成最早结束的因为最早结束的会议结束时间不晚于任意会议不会增加冲突所以替换后仍然是最优解。接着对第二场、第三场做同样的事就能把任意最优解“洗”成贪心解。1.4 我给自己定的贪心自查清单拿到一道题怀疑能贪心时我会先过四个问题全部通过才敢写能不能一个反例干掉先想在极端情况下比如所有值都相等、所有物品体积相同、时间窗口恰好重叠。我的“局部最优”有没有一个明确的比较指标如果连“怎么算当前最优”都说不清楚基本不是贪心题。做完一个决定后会不会影响后续所有决定的可用范围如果影响很大大概率要动态规划而不是贪心。最优解结构是否是“一条链走到底”动态规划需要维护一个状态集合贪心只维护一个状态。能明显看出“只维护一个变量就能推出最终答案”的贪心的概率更高。2. 二分查找的边界之痛从“背模板”到“懂不变量”二分查找这个问题几乎每个人都能写出大概但错起来也是千奇百怪。最常见的死法有三种死循环、越界返回错误下标、左右边界弄反。这些问题的根源只有一个你只记住了 while 里写 l r 还是 l r却没有定义清楚你的搜索区间到底是什么。2.1 先说清楚“区间不变量”二分查找的本质不是“折半找数”而是维护一个关于答案范围的区间不变量。随便找一句代码里都有隐含的约定。比如左闭右开区间写法[l, r)下标 0 到 l-1 区间内的元素已经被判断为“不可能是答案”下标 r 到 n-1 区间内的元素也已经被排除答案只可能在[l, r)中有了这个不变量每次循环怎么改就变得有逻辑a[mid] target时mid 可能是答案但它右边不可能有“第一个 target”的位置所以把 r 收缩到 mida[mid] target时mid 及左边全部不可能所以把 l 拉到 mid 1。我强烈建议你在草稿纸上把l、r、mid的位置画出来标出哪个区间是“已知不可能”哪个区间是“答案所在”。写二分时先写一行注释// 答案在 [l, r] 中l 初始化为最小可能r 初始化为最大可能。坚持这样做比背任何模板都管用。2.2 三个可以直接抄的二分模板模板一找第一个 target的位置也就是 C 里lower_bound的语义。int lower_bound(vectorint a, int target) { int l 0, r a.size(); // 左闭右开 while (l r) { int mid l (r - l) / 2; if (a[mid] target) r mid; else l mid 1; } return l; // 如果等于 n说明没有元素 target }模板二找最后一个 target的位置也就是 upper_bound 的前一个位置。int last_le(vectorint a, int target) { int l 0, r a.size() - 1; while (l r) { int mid (l r 1) / 2; // 注意这里是向上取整 if (a[mid] target) l mid; else r mid - 1; } return l; }这两个模板最核心的区别在于当条件满足时是让r mid还是l mid。第一个模板满足条件收缩右边界所以 mid 取左中位就能保证l r时循环必然推进第二个模板满足条件时收缩左边界如果 mid 还取左中位遇上l 0, r 1时mid 0满足条件后l原地不动就死循环了。所以第二个模板强制使用(l r 1) / 2向上取整。很多人背模板记不住那个1就是因为不知道这个“为什么”。你只需要记住一句话当你的逻辑里出现“满足条件就l mid”时mid 必须向上取整否则可能死循环。这个规律比背模板本身更重要。模板三浮点数二分直接迭代固定次数。double lo 0, hi 1e9; for (int i 0; i 100; i) { double mid (lo hi) / 2; if (check(mid)) hi mid; else lo mid; }浮点数二分不建议用hi - lo eps作为循环条件因为你不知道 eps 设多大才够设大了精度不够设小了可能循环时间过长。固定迭代 100 次在 64 位 double 下已经能收敛到机器精度附近既稳定又省心。2.3 从“二分查找”到“二分答案”只差一步如果你以为二分只能用来在有序数组里找元素那就浪费了这个工具。二分查找的核心推广叫“二分答案”题目要求你求一个最优化数值只要这个问题的可行解随着数值大小呈现单调性你就可以在答案的取值范围内做二分逐步逼近最优值。举个例子题目问“最大能切成多长的木段”你不需要直接计算答案你只需要不断猜测一个长度 X然后去验证“能不能做到”。这个猜的过程就是二分查找验证的过程常常就是贪心。到这个点贪心和二分就算正式认识了。3. 二分答案 贪心验证解决“最大化最小值 / 最小化最大值”的万能框架原因很简单这类问题直接构造最优解往往毫无头绪但给定一个候选值 X 问“能否做到”时问题通常变得具体又直观。只要验证函数是单调的二分会帮你把过程太平顺。3.1 把“求最优值”翻译成“判断可行性”拿到这类问题时我第一步永远是在纸上写两行原问题最大/最小化某个变量 ans子问题给定一个值 X判断是否存在一种方案使得“这个变量”能不超过/不低于 X如果这个判断函数check(X)在 X 很小时为假、在 X 很大时为真或者反过来并且 X 从假到真的切换只有一次那就可以二分。举个例子你有 n 根木头的长度想切成至少 k 段长度完全相同的短木段求每段最大能有多长。原问题看起来要处理各种长度的组合很麻烦。但子问题瞬间变简单给定一个候选长度 X把每根木头能切出来的段数len / X加起来如果总段数大于等于 k就说明 X 可行。由于总段数随着 X 增大只减不增可行性从真变假也只有一次拐点所以可以二分。3.2 check 函数为什么常常要用贪心给定 X 之后很多约束会变得特别“局部”。比如“段数至少 k 段”对每根木头能多切就多切就是最优没有任何理由少切比如“把数组分成 m 段每段和都不超过 X问最少要分几段”从左往右能放就放也是最优。这里的贪心不是拍脑袋而是因为验证目标往往是“在不突破某个上限/下线的前提下尽量让某个约束最松”。当目标变成“够不够”“行不行”时贪心往往就能给出可证的最优决策而我总是强调先证明“能放就放”不会导致更坏结果再写循环。3.3 完整案例切木段问题题目数组woods [10, 24, 8, 15]单位长度需要至少切出k 7段长度完全相同的木段问最大段长是多少。验证函数bool check(int x, int k, vectorint woods) { if (x 0) return true; // 长度为0永远可行但实际输出不会取0 long long cnt 0; for (int w : woods) { cnt w / x; if (cnt k) return true; } return cnt k; }二分的取值区间可以直接定为[0, 最大的那根木头长度]。因为每段长度不可能超过原始木头的最大长度也不可能为负。套用“找最后一个可行值”的结构int l 0, r *max_element(woods.begin(), woods.end()); while (l r) { int mid (l r 1) / 2; if (check(mid, k, woods)) l mid; else r mid - 1; } // 这里会得出 7用这段数据手动推一下mid 取 12 时4 根木头分别切出 0、2、0、1 段合计 3 段不可行mid 取 6 时分别 1、4、1、2 段合计 8 段可行mid 取 7 时分别 1、3、1、2 段合计 7 段仍然可行mid 取 8 时分别 1、3、1、1 段合计 6 段不可行。所以最优答案是 7。整个过程不需要尝试所有可能复杂度很低。3.4 完整案例按顺序分组的最小化最大值再看另一类典型有一个数组a[1..n]要按顺序切成 m 段连续子段要求这 m 段各自的元素和的最大值尽可能小。这类问题的口语化场景特别多把 n 个按顺序提交的任务分给 m 个并行处理器希望负载最重的那个处理器尽可能轻松把 n 页文档按顺序分给 m 个人誊写希望最累的人干的活尽量少。这里先想清楚单调性如果给每段设一个“和的上限 X”那么 X 越大能塞进一段的任务就越多总段数就越少。我们要找的是“在总段数不超过 m 的前提下X 的最小值”。验证函数用贪心从左往右扫描bool canSplit(const vectorlong long a, int m, long long x) { int seg 1; long long cur 0; for (long long v : a) { if (v x) return false; // 单个任务就超上限直接不可行 if (cur v x) { seg; cur v; if (seg m) return false; } else { cur v; } } return seg m; }“能放就放”在这里为什么是对的因为我们的目标是让总段数尽量少在每段和不超过 x 的情况下把当前元素塞进当前这段不放下一段绝不会让总段数变多。塞得越满留给后面的元素空间越少但这会影响的是“后面某一段的长度”不会影响总段数的最优性——只要段总数不超 m段之间的松紧完全不重要。这又是一个标准的贪心验证。二分的下界可以直接取max(数组的最大元素, ceil(总和 / m))因为这两点是最低要求上界取所有元素之和。然后long long lo max(maxVal, (sum m - 1) / m); long long hi sum; while (lo hi) { long long mid lo (hi - lo) / 2; if (canSplit(a, m, mid)) hi mid; else lo mid 1; } // lo 就是最小化后的最大子段和这种“先设上界再二分”的方式能把枚举最优解的时间从 O(2^n) 量级压到 O(n log sum)n 是数组长度。n 到几十万也扛得住前提是你选对二分方向并写对验证函数。3.5 怎么判断我该用哪个二分模板这是一个非常容易迷糊的地方。我的口诀很简单如果你要“最大化一个可行的 X”即 X 越大越难可行那就在可行域里找最后一个可行值用“满足条件就l mid”的模板mid 向上取整。如果你要“最小化一个可行的 X”即 X 越大越容易可行那就在可行域里找第一个可行值用“满足条件就r mid”的模板mid 向下取整。记住这个方向然后每次都把check函数先写出来再回来看这个口诀比硬背模板更不容易错。4. 实战拆题二分查找函数题与二分答案综合题的常见坑现在很多 OJ 平台和课程网站比如 PTA会在基础题里直接要求你实现二分查找函数。这类题目代码量不大但非常考细节因为题目的返回值定义五花八门。4.1 PTA 风格的二分查找函数为什么不能盲目抄模板PTA 上常见的函数题会这样描述给定一个升序数组和待查找元素 x若找到返回下标找不到返回 -1。这种要求下用最简单的l r三路分支写法最稳妥int binarySearch(int a[], int n, int x) { int l 0, r n - 1; while (l r) { int mid l (r - l) / 2; if (a[mid] x) return mid; else if (a[mid] x) l mid 1; else r mid - 1; } return -1; }但有些变体题目问的是“第一个等于 x 的位置”或“最后一个等于 x 的位置”这时候上面的代码就不够了。比如有序数组[1, 2, 2, 2, 3]找第一个 2 应该返回 1找最后一个 2 应该返回 3而普通三路分支返回的可能是 2。我建议碰到这类函数题先审题三件事数组是左闭右开还是左闭右闭索引要求返回的是任意一个匹配、第一个匹配、最后一个匹配还是找不到时的插入位置如果数组为空返回值约定是什么把这些弄清再选择下面的模板找第一个匹配用前面模板一找最后一个匹配用前面模板二找不到返回 -1 则在外层判断一下。4.2 一道综合题告诉你“二分答案”怎么落地题目大意给定 n 个值班时间段长度按顺序排好你希望把这些时间段合并成至多 m 个大区间每个大区间的总时长不能超过某个值 X求所有大区间时长上限的最小值。这就是刚才那个序列分割问题。我把它搬到具体场景里是为了让你看清楚题目里那些报表、任务、日志、日程本质上都是数组所谓“最多 m 组”就是在考canSplit的段数判断。代码结构很清晰#include bits/stdc.h using namespace std; bool canSplit(const vectorlong long a, int m, long long x) { int seg 1; long long cur 0; for (long long v : a) { if (v x) return false; if (cur v x) { seg; cur v; } else { cur v; } if (seg m) return false; } return true; } int main() { int n, m; cin n m; vectorlong long a(n); long long sum 0, mx 0; for (int i 0; i n; i) { cin a[i]; sum a[i]; mx max(mx, a[i]); } long long lo max(mx, (sum m - 1) / m); long long hi sum; while (lo hi) { long long mid lo (hi - lo) / 2; if (canSplit(a, m, mid)) hi mid; else lo mid 1; } cout lo endl; return 0; }注意几点实战细节数组元素、总和、二分变量全部用long long因为这种题的构造数据经常让 int 溢出。seg初始化为 1不是 0因为我们至少有一个区间。如果v x直接返回 false规避了“单个点无法放入任何区间”的边界。如果你做的题要求输出具体怎么分组那还需要在canSplit可行的前提下再贪心划分一次把每组边界记录到数组里。这个扩展我在工程里用过很多次因为产品要的不只是“能不能”而是“怎么分”。4.3 一道优选的“最大化最小”变体把球放到桶里再看另一种常见结构有 m 个球和 n 个空位空位坐标在一条直线上球和球之间必须隔开至少 dist 的距离问 dist 最大能是多少。这类题可以换个包装出现在很多地方只要问题提到“相邻间隔的最小值最大”基本就是它。原问题如果用暴力得枚举所有 C(n, m) 种放法n 稍微大一点就炸。改成二分答案就舒服多了二分 dist查“能不能放完 m 个球”。check(dist)依然用贪心第一个球放在最左边的空位之后每次找“下一个距离当前位置 dist 且最靠左的空位”能放就放最后统计放了几个。这个贪心的正确性和活动选择非常像尽早占用靠左的位置永远比往后挪一个位置更优因为往后挪只会减少后面球的选择余地。bool canPlace(vectorint pos, int m, int dist) { int count 1, last pos[0]; for (int i 1; i pos.size(); i) { if (pos[i] - last dist) { count; last pos[i]; if (count m) return true; } } return count m; }然后二分的下界是 0上界是最后一个空位和第一个空位的差。只要canPlace(mid)为真就试试更大的 mid所以套“最后可行值”模板。到这里你应该能感觉到所谓难题其实就是“贪心验证 二分答案”的组合拳。5. 我踩过的坑二分死循环、贪心错判与对拍调优三板斧写算法题不看别人踩坑自己总要踩一遍。我把最常见的几个坑列出来每个都有真实翻车场景希望能帮你省掉一晚上调试时间。5.1 二分死循环的三种典型表现第一种满足条件时l mid但 mid 是向下取整。比如区间只有两个候选值l 0, r 1, mid 0check(0) 为真于是 l 还是 0死循环。这种最容易在“找最后一个可行值”的模板里出现解决办法就是 mid 向上取整。第二种把大于等于写成大于。尤其找“第一个 target”时条件应该是a[mid] target你一偷懒写成遇到 target 本身在数组中时就可能跳过正确位置。第三种区间开闭混用。比如左闭右开写习惯了换到另一个函数里又用r mid - 1或者l mid 1越界。我的建议是写二分前先固定一种区间约定最好全程左闭右闭配套while (l r)或全程左闭右开配套while (l r)。不要在一个函数里反复切换。如果不幸死循环在循环里加一行printf(l%d r%d mid%d, l, r, mid)看 l 和 r 有没有某一轮完全没动。一旦看到l和r在某步收缩后没变基本就是取整方向错了。5.2 贪心题错了最有效的排错方法是对拍贪心题最大的问题是样例过了一提交就 WA而且你根本不知道哪个测试点挂了。这时候最快的不是人肉找反例而是写一个对拍程序。对拍三板斧写一个非常慢但绝对正确的暴力解法比如枚举所有情况、动态规划、DFS。写一个随机数据生成器数据范围小一点比如 n 不超过 10数值不超过 20。无限循环生成数据分别跑暴力解和贪心解一旦发现答案不一致立刻把数据打印出来。拿找零钱那个例子你只要让随机面额和随机总额跑 1000 组大概率很快就会发现贪心输出比暴力多枚硬币的那个样例。这个反例会瞬间击碎你的“这题太简单了”的幻觉也会帮你快读定位到贪心策略失效的真正原因。现在很多 OJ 平台都有自带的“随机数据 暴力对拍”功能原理和我上面说的一模一样。你在本地写一个 Python 脚本做对拍甚至不需要很强的基础用一个脚本生成数据另一个脚本调用两个可执行文件比对 stdout。5.3 关于复杂度和过大数据的几个体感经验二分答案的复杂度是 O(n log range)。range 很大时比如答案范围是 0 到 1e9log 也就 30 左右配合 O(n) 的 check总复杂度也就 3000 万级别1 秒左右能跑完。所以看到 n 是 10 万、20 万范围到 1e9不用慌。但要注意 check 函数内部千万别写太重的操作。我有一次在 check 里对数组做了排序导致整体复杂度直接变成 O(n log n log range)数据稍大就超时。后来把 check 改成一遍扫描速度立刻上来。记住check 尽量保持 O(n)甚至能在扫描过程中提前终止就提前终止。另外整数二分的上下界还会影响收敛速度。比如切木段问题上界直接用最大木头长度就行没必要从 1e9 开始。上界越紧循环次数越少虽然 log 差距不大但在真实竞赛里就是那么零点几秒的事。5.4 一个我常用的收益很高的习惯先写注释再写代码针对这类“二分答案 贪心验证”的题我现在会先在代码顶部写三行注释// 1. 我要最大/最小化的变量是什么 // 2. 给定 Xcheck(X) 怎么判断可行性返回真表示 X 可行。 // 3. 随着 X 增大check 的真假方向是什么写完这三行再动手写代码写错概率下降一大半。因为二分模板的最大坑就是你根本没想清楚真假方向却已经开始改边界了。方向搞反l 永远推不动方向搞对剩下的就是把模板往代码里填。5.5 这两个技能在工作里的实际用处可能有人觉得贪心和二分只是面试和考试里的玩具实际上工作中也有用处。我遇到过真实需求有一批日志文件按时间顺序排列需要按大小切分成尽量少的归档包同时每个包不能超过某个大小上限。这就是典型的最小化最大值问题直接套二分答案 贪心验证轻松解决。另一次是资源调度有一批任务按优先级顺序执行要分给若干个执行线程让最慢的线程尽量早结束。和上面那个问题一模一样。我当时的同事还在手写动态规划我说这题能二分三十分钟后给出方案效果很好。算法不是用来表演的是用来在关键时刻救场的。结尾一些来自实战的碎碎念写到这里最想分享的其实不是某个模板而是一种做题心态。贪心和二分看似是两个知识点但真正好用的地方恰恰在它们的组合上。每当你遇到一个“求最大/最小某个值并且这个值有一点范围”的问题都值得先问自己能不能二分答案如果能check 函数能不能用贪心写这两个问题的答案常常比你在状态转移方程里纠结半天的收益大得多。我自己的习惯是每道这样的题都保留一份“错误记录”死循环、边界超限、方向写反都截图存下来。第二次遇到同类题目时先翻一遍这些记录踩坑率能降很多。代码是练习出来的也是总结出来的。希望这篇文章能让你少走一圈弯路直接站到正确的那条路上然后去踩那些更有价值的坑。