“贪心策略”和“二分查找”，名字听起来一个像“差不多先生”，一个像“绝对严谨的尺子”，但我在实际刷题和带新人时发现，这两者不仅不是对立的，反而经常是黄金搭档。很多人单学贪心时觉得太简单：每步选最优而已嘛；单学二分时又觉得太繁琐：边界到底是左闭右闭还是左闭右开，背了忘、忘了背。可一旦把这两个东西合在一起，用“二分答案 + 贪心验证”去解那些“最小化最大值”“最大化最小值”的题目，整个思路就会顺畅很多。
这篇文章不需要你有多深的算法基础，我会从贪心到底什么时候成立讲起，再拆二分查找里最容易翻车的边界问题，最后用一个通用套路把两者缝合起来。无论你是在准备考试、刷 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 步贪心是最优的，再证明第 k+1 步贪心选择仍然是最优的。
- 交换论证法：假设存在一个最优解，它某一步没有采用贪心方案。证明把这个最优解里的对应元素“交换”成贪心方案后，结果不会变差甚至更好。反复交换，就能得到“存在一个最优解完全等于贪心解”。
- 反证法：假设贪心解不是最优，推导出矛盾。
我实际写题时，一般先在纸上用交换论证。活动安排就是典型：任意最优解中，第一场会议如果不是最早结束的那场，就把它换成最早结束的，因为最早结束的会议结束时间不晚于任意会议，不会增加冲突，所以替换后仍然是最优解。接着对第二场、第三场做同样的事，就能把任意最优解“洗”成贪心解。
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 收缩到 mid；a[mid] < target时，mid 及左边全部不可能，所以把 l 拉到 mid + 1。
我强烈建议你在草稿纸上把l、r、mid的位置画出来，标出哪个区间是“已知不可能”，哪个区间是“答案所在”。写二分时先写一行注释：// 答案在 [l, r] 中，l 初始化为最小可能，r 初始化为最大可能。坚持这样做，比背任何模板都管用。
2.2 三个可以直接抄的二分模板
模板一：找第一个>= target的位置，也就是 C++ 里lower_bound的语义。
int lower_bound(vector<int>& 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(vector<int>& 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, vector<int>& 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 vector<long 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 vector<long 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; vector<long 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(vector<int>& 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 = 0，check(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 到 1e9，log 也就 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. 给定 X，check(X) 怎么判断可行性？返回真表示 X 可行。 // 3. 随着 X 增大，check 的真假方向是什么？写完这三行再动手写代码，写错概率下降一大半。因为二分模板的最大坑就是你根本没想清楚真假方向，却已经开始改边界了。方向搞反，l 永远推不动；方向搞对，剩下的就是把模板往代码里填。
5.5 这两个技能在工作里的实际用处
可能有人觉得贪心和二分只是面试和考试里的玩具，实际上工作中也有用处。我遇到过真实需求：有一批日志文件按时间顺序排列，需要按大小切分成尽量少的归档包，同时每个包不能超过某个大小上限。这就是典型的最小化最大值问题，直接套二分答案 + 贪心验证，轻松解决。
另一次是资源调度，有一批任务按优先级顺序执行，要分给若干个执行线程，让最慢的线程尽量早结束。和上面那个问题一模一样。我当时的同事还在手写动态规划，我说这题能二分，三十分钟后给出方案，效果很好。算法不是用来表演的，是用来在关键时刻救场的。
结尾：一些来自实战的碎碎念
写到这里，最想分享的其实不是某个模板，而是一种做题心态。贪心和二分看似是两个知识点，但真正好用的地方恰恰在它们的组合上。每当你遇到一个“求最大/最小某个值，并且这个值有一点范围”的问题，都值得先问自己：能不能二分答案？如果能，check 函数能不能用贪心写？这两个问题的答案，常常比你在状态转移方程里纠结半天的收益大得多。
我自己的习惯是每道这样的题都保留一份“错误记录”：死循环、边界超限、方向写反，都截图存下来。第二次遇到同类题目时，先翻一遍这些记录，踩坑率能降很多。代码是练习出来的，也是总结出来的。希望这篇文章能让你少走一圈弯路，直接站到正确的那条路上，然后去踩那些更有价值的坑。
