二分查找与二分答案：模板、边界、死循环及变体实战

带过几届校招和暑期实习的算法辅导后，我发现一个很奇怪的现象：几乎所有人在被问到"你会二分吗"的时候都会点头，但真让他们在白板上写一个不带bug的二分，能一次过的不到三成。二分查找算法看着只有五六行，却是整个基础算法里"眼会手不会"最严重的重灾区。它能做的事情远比"在有序数组里找个数"多得多——从有序数组定位、边界查找，到旋转数组、峰值判定，再到把一整类"求最大最小值"的优化问题变成判定问题，背后都是同一套思想在不同场景下的变形。这篇东西就是把我这些年讲二分、写二分、以及帮别人改二分时积累的那点经验全部摊开，不管你是刚学完数组的新手，还是做题时被l和r折磨过的老手，都能从中找到能直接抄走的东西。

1. 二分的骨架不是"折半"，而是把答案锁进一个区间

1.1 从猜数字游戏看二分真正在干什么

大多数教材引入二分都喜欢用猜数字：1 到 100 之间想一个数，你每次猜一个，我只告诉你"大了""小了""对了"。这个游戏的最优策略是每次猜当前范围的中点，最多 7 次必中。很多人的理解就停在这里——"二分就是每次砍一半"。

这个理解不算错，但太浅，浅到一旦题目换了个外套你就认不出来。我更愿意这样描述二分的内核：维护一个"答案一定落在其中"的候选区间，每一轮用一个单调的判定条件，把候选区间砍掉一半。注意这里的两个关键词——候选区间、单调判定。折半只是手段，砍掉哪一半才是真正需要思考的地方。

猜数字游戏里，判定条件是"你猜的数比目标大还是小"，这个条件天然单调：猜的数越大，越容易"太大了"。所以当我们猜mid得到"太小了"的回答时，可以确定答案一定在mid的右边，于是l = mid + 1。整套流程是自洽的。

换成"在旋转有序数组里找目标值"呢？数组整体不再有序，但判定条件依然存在——mid落在哪一段，目标值在不在这段里。你会发现二分的形状完全没变，变的只是那个if里写什么。这就是我建议的学习顺序：先吃透"维护候选区间"这个抽象模型，再去看各种变体，你会发现它们全是同一个模子里刻出来的。

1.2 一次砍一半，到底省了多少次计算

二分的时间复杂度是 O(log n)，这个结论人人都背，但真正理解它需要把推导跑一遍。假设候选区间长度是 n，每轮之后变成 n/2、n/4、n/8……直到长度变成 1，设需要的轮数是 k，那么：

n / 2^k = 1 => 2^k = n => k = log2(n)

代入具体的数量级感受一下：n 等于 10 万时，log2 大约是 17；n 等于 100 万时，大约是 20；n 等于 10 亿时，也不过 30 次。这意味着一个 10 亿规模的数组，二分只需要比较 30 次，而线性扫描要 10 亿次。这个差距不是"快一点"，是"能不能跑完"的区别。

但这里有个极易被忽略的坑：log n 只是"层数"，真实复杂度是层数乘以每层的工作量。如果每一层的判定函数check本身需要 O(n) 的时间，那整体复杂度是 O(n log n)，不是 O(log n)。这在"二分答案"类题目里特别常见——有人上来就说"这题二分，O(log n) 秒了"，结果 check 里套了个遍历，实际跑起来比暴力还慢。我在复盘别人的代码时，看到过不止一次因为误判复杂度而选错算法的例子。

所以正确的思维习惯是：先确定每一轮判定是常数级还是线性级，再算总账。判定是常数级（比如比大小、取数组某个位置的值），就是 O(log n)；判定需要遍历，就老老实实乘上那个 n。

1.3 单调性是二分的唯一通行证，它不是"数组有序"

这句话我要重复三遍：二分的前提不是数组有序，是存在单调的判定条件。

数组有序只是最方便的一种构造方式。举个例子，在 [1, 3, 5, 7, 9] 里找 5，我们用的判定是a[mid] < 5，数组有序保证了"如果 a[mid] < 5，那么 mid 左边所有元素都小于 5"，这个性质让判定结果能直接翻译成区间收缩的方向。但如果数组是 [1, 5, 3, 7, 9]，你还能用这个判定吗？不能，因为 a[mid] 小于 5 不代表左边全部小于 5，区间收缩就失去了依据。

反过来，某些数组整体无序，但存在局部单调结构，二分照样能上。最典型的是旋转有序数组 [4, 5, 6, 7, 0, 1, 2]，它不是有序数组，但任意切一刀，至少有一半是有序的，我们可以先判断哪一半有序，再判断目标值是否落在这一半的数值范围内，从而决定往哪边收缩。

判断一道题能不能用二分，我的检验方法是问自己：能不能找到一个判定函数 f(x)，使得存在一个分界点 k，所有 x <= k 时 f(x) 为真，所有 x > k 时 f(x) 为假（或者反过来）。能找到，二分就能用；找不到，别硬上，通常会翻车。这个判定函数在"数组查找"场景里是"元素值小于目标"，在"二分答案"场景里是"某个猜测值是否可行"，形式不同，本质一样。

2. 整数二分的两套模板，各自负责什么活儿

2.1 闭区间模板：l 和 r 都指向"可能的答案"

闭区间写法里，l和r都代表候选区间内的合法下标，区间是[l, r]。每轮循环条件是l <= r，当l > r时区间为空，循环结束。

// 在有序数组 a 中查找 target，返回下标，找不到返回 -1 int l = 0, r = n - 1; // 候选区间 [l, r] while (l <= r) { int mid = l + (r - l) / 2; // 防止 l + r 溢出 if (a[mid] == target) { return mid; } else if (a[mid] < target) { l = mid + 1; // 答案只可能在右半边 } else { r = mid - 1; // 答案只可能在左半边 } } return -1;

这套写法的优点是直观：l、r就是两个真实的数组下标，脑补区间收缩的画面非常自然，适合刚接触二分的人先建立直觉。它的终止条件是l > r，也就是区间彻底空了。

但它在"找边界"的场景里就有点力不从心了。比如要找"第一个大于等于 target 的位置"，闭区间模板里没法直接返回一个不存在于数组中的位置（比如 n），需要额外处理，代码会变丑。所以实际做题时，我更常推荐下面这套。

2.2 左闭右开模板：为什么老手都偏爱 [l, r)

左闭右开区间写作[l, r)，含义是l是候选区间内的合法下标，r是候选区间外的第一个位置，也就是"哨兵"。它的好处是：r可以取到 n，天然能表示"答案在数组末尾之外"，这在找边界时非常关键。

// 返回第一个 >= target 的位置；若全部小于 target，返回 n int l = 0, r = n; // 候选区间 [l, r) while (l < r) { // 区间非空时继续 int mid = l + (r - l) / 2; // 下取整，保证 mid < r if (a[mid] < target) { l = mid + 1; // mid 及左边都不可能是答案 } else { r = mid; // mid 有可能是答案，保留 } } return l; // 此时 l == r，即第一个满足条件的位置

这套模板的细节值得掰开揉碎讲。一是循环条件是l < r，因为区间[l, r)为空的条件正是l == r。二是r = mid而不是r = mid - 1，理由是a[mid] >= target时，mid自己可能就是我们要找的那个"第一个 >= target"的位置，不能把它丢掉。三是mid必须向下取整，否则会越界——这一点我在下一节展开。

"第一个大于等于"和"第一个大于"其实是同一个模子，只要把if里的比较改成a[mid] <= target，就变成了返回第一个严格大于 target 的位置。这两个操作分别对应 C++ 标准库里的lower_bound和upper_bound，理解了这套模板，那俩函数就不再是"背下来的工具"，而是你能手写的东西。

2.3 lower_bound 和 upper_bound 的边界差异

这两个函数在实战里用得极频繁，但很多人在边界上栽跟头。看这张对照表：

可以看到，upper_bound(lower_bound)这组返回值可以直接算出目标值在数组中的出现次数：upper_bound - lower_bound。这个技巧在处理"统计某个值出现频率""找出某个值的区间范围"这类问题时特别好用，比手写两次二分再处理边界要干净得多。

但要注意一个陷阱：当lower_bound返回 n 时，直接拿它当下标去访问数组会越界。我见过不少人在合并区间、在线段树上套用二分时忘了判这个 n，导致莫名其妙的运行错误。稳妥的做法是拿到返回值后先检查是否等于 n，或者用迭代器版本让标准库帮你处理。

3. 死循环和下标越界：二分最常翻车的两个地方

3.1 mid 的取整方向必须和区间更新方式配对

这是所有二分 bug 里排名第一的元凶，没有之一。我把规则总结成一句话：

区间更新里出现r = mid（右边界不收缩到 mid 左边），mid 必须向下取整；区间更新里出现l = mid（左边界不收缩到 mid 右边），mid 必须向上取整。

为什么？用一个极小的例子推一遍就明白了。假设当前l = 0, r = 1，如果 mid 向下取整，mid = 0。此时如果代码写的是l = mid，那么新的l还是 0，区间[0, 1]一点没变，下一轮还是算出一模一样的 mid，程序就卡死了。

用表格把四种组合列清楚，写错的时候对照着看：

换成常用的口诀就是：求最小的可行值时用下取整配r = mid，求最大的可行值时用上取整配l = mid。这两套写法覆盖了绝大多数的整数二分需求，把它们刻进肌肉记忆，比每次现场推导可靠得多。

3.2 写完之后必须手动验证的四种边界

代码写完不代表完事，我在白板上写二分之后一定会过一遍这四个场景，它们能挡掉九成的隐藏 bug。

第一种是空数组，n = 0。这时候l = 0, r = 0（左闭右开模板），循环条件l < r不成立，直接返回l = 0。这个返回值是否符合预期？在lower_bound的语义下，空数组里任何元素的插入位置都是 0，是对的。

第二种是单元素数组，判断它对 target 的三种关系（小于、等于、大于），看返回值是不是分别等于 0、0 或 1、1。这一步能暴露出r = mid和r = mid - 1写混的问题。

第三种是目标值小于所有元素，也就是答案落在区间最左端。左闭右开模板应该返回 0，闭区间模板则应该返回 -1 或者 0（取决于你在找什么）。如果返回了别的值，说明左边界收缩有问题。

第四种是目标值大于所有元素，答案落在区间最右端之外，左闭右开模板应该返回 n。这是闭区间模板最容易出错的地方，因为没有n这个合法下标可用，很多人会错误地返回n - 1。

把这四种情况写成小测试用例本地跑一遍，成本极低，收益极高，比事后 debug 半小时划算多了。

3.3 用对拍和打印把问题钉死在具体某一轮

当二分的结果怎么调都不对的时候，别再盯着代码发呆，直接上对拍。思路很简单：写一个 O(n) 的暴力版本作为标准答案，然后随机生成大量小规模数据，两个程序同时跑，比较输出。

// 暴力版本：线性扫描找第一个 >= target 的位置 int bruteForce(vector<int>& a, int target) { for (int i = 0; i < (int)a.size(); i++) { if (a[i] >= target) return i; } return (int)a.size(); } // 对拍主逻辑 int main() { mt19937 rng(12345); for (int t = 0; t < 100000; t++) { int n = rng() % 10; // 小规模，方便复现 vector<int> a(n); for (int i = 0; i < n; i++) a[i] = rng() % 10; sort(a.begin(), a.end()); // 保证有序 int target = rng() % 10; int got = lowerBoundTemplate(a, target); int expect = bruteForce(a, target); if (got != expect) { printf("FAIL: n=%d target=%d got=%d expect=%d\n", n, target, got, expect); for (int x : a) printf("%d ", x); return 0; } } printf("ALL PASS\n"); return 0; }

这段脚本的威力在于：小规模随机数据能在几秒内覆盖你手写测试根本想不到的组合。我个人习惯是把数据范围压到 0 到 10 之间，这样一旦失败，输出出来的数组短得能直接在纸上重演一遍，定位速度比大数据的对拍快得多。

另一个土办法是在循环里打印状态，但要注意别在正式提交的代码里留着——我就干过这事儿，交上去直接大规模超时，因为打印本身的开销在百万级循环里是灾难。

4. 浮点二分：精度这件事，写死循环次数比写 epsilon 靠谱

4.1 固定迭代次数为什么比 eps 判定更稳

浮点二分的场景通常是"求解一个实数 x，使得某个关于 x 的单调函数满足条件"，比如求方程的根、求几何问题里的最优长度。新手最爱写的版本是这样的：

double l = 0, r = 1e9; while (r - l > 1e-8) { // 看起来没问题 double mid = (l + r) / 2; if (check(mid)) r = mid; else l = mid; }

这段代码在大多数情况下能跑，但有两个隐患。第一个隐患是当l和r的量级很大时，比如都在 1e9 附近，double 的有效数字只有大约 15 到 16 位十进制数字，这时候r - l已经小到无法再被有效表示，mid算出来可能等于l或者r，区间再也缩不动，循环就永远停在r - l > 1e-8这个条件上。第二个隐患是check函数在临界点附近可能因为浮点误差产生抖动，导致收敛方向来回横跳。

更稳的写法是固定迭代次数：

double l = 0, r = 1e9; for (int i = 0; i < 100; i++) { // 固定 100 轮 double mid = (l + r) / 2; if (check(mid)) r = mid; else l = mid; } // 此时 r 就是答案，误差不超过初始区间长度除以 2 的 100 次方

为什么 100 轮绝对够？初始区间长度是 1e9，每轮减半，100 轮之后长度是 1e9 / 2^100，这个数字远远小于 double 能表示的最小相对精度（约 2 的负 52 次方，量级是 1e-16）。换句话说，迭代到 60 轮左右的时候，区间长度就已经缩小到 double 表示不出来差异的地步了，后面的迭代纯属浪费。所以 100 是一个"肯定安全但略有余量"的选择，完全不用纠结。

4.2 迭代次数怎么估算，以及 eps 到底该取多少

如果你就是想知道"够用的最小轮数"，可以按这个公式估：

所需轮数 k = ceil(log2(初始区间长度 / 目标精度))

举两个例子。初始区间 1e9，目标精度 1e-6，那么 1e9 / 1e-6 = 1e15，log2(1e15) 约等于 49.8，向上取整是 50 轮。再加一点安全余量，写 60 轮就很稳妥了。初始区间是 1e4，目标精度 1e-9，比值是 1e13，log2 约等于 43.2，取 50 轮。

如果题目确实要求用 eps 判定，我的建议是 eps 取到比题目要求精度再小两个数量级。题目要求精确到 1e-6，那你循环条件就写r - l > 1e-8。原因很简单：eps 只是区间长度的判据，而输出时你还要再做一次取整或者比较，中间会有一次精度损失，留两个数量级的余量能有效避免"答案差最后一位"的悲剧。

还有一个细节是输出。浮点二分的答案一般输出l或r都行，两者差距在精度范围内，但要注意题目要求的输出格式——有时候是向下取整，有时候是四舍五入，有时候是保留几位小数。我吃过一次亏：算法完全正确，就因为输出时用了printf("%.2f")而题目要求的是向下取整，判了错。

5. 二分答案：把"求最优解"翻译成"判断某个值行不行"

5.1 什么题目能用二分答案，怎么识别

二分答案是一类题目的统称，特征是：题目要求最大化或最小化某个值，而这个值的好坏可以通过一个单调的判定函数来检验，但最优值本身没法直接算出来。这时候我们就"猜"一个答案，检验它行不行，然后根据检验结果收缩猜测范围。

识别这类题有个很好用的信号——题目里出现"最大的最小值""最小的最大值"这种绕口的表述，基本就是二分答案。比如"要让所有牛之间的最小距离最大"、"要在 m 个月内完成所有任务、求每个月最大工作量最小是多少"、"砍树得到至少 m 米木材、求锯片最高能设多高"，都是同一类。

这类题的核心工作量其实不在二分本身，而在那个check函数怎么写。二分部分永远是那十行不到的模板，check则是每道题都不一样。所以做题时的时间分配应该是：想清楚单调性在哪、check怎么写，然后用模板三分钟糊出二分框架。

5.2 求最小值还是最大值，两套模板别搞反

二分答案的两套模板，正好对应整数二分里那两条规则。

求"最小的可行值"（比如最少需要多少天、最小的最大负载）：

int l = 下界, r = 上界; // 保证答案落在 [l, r] 内 while (l < r) { int mid = l + (r - l) / 2; // 下取整 if (check(mid)) { r = mid; // mid 可行，答案不超过 mid } else { l = mid + 1; // mid 不可行，答案必须更大 } } return l;

求"最大的可行值"（比如锯片最高能设多高、最小距离最大是多少）：

int l = 下界, r = 上界; while (l < r) { int mid = l + (r - l + 1) / 2; // 上取整 if (check(mid)) { l = mid; // mid 可行，答案至少是 mid } else { r = mid - 1; // mid 不可行，答案必须更小 } } return l;

这两段代码我建议直接背下来，因为在实际做题时现推特别容易把取整方向和更新方向搭错。背下来之后，剩下所有精力都可以投在check上，那才是决定能不能 AC 的地方。

5.3 完整走一遍砍树这道经典题

拿一道最经典的题走完全流程，感受一下整个思考链条。题目大意是：有 n 棵树，第 i 棵高度为 h[i]，你需要得到总长至少 m 的木材，锯片高度设为 H，每棵树被锯掉的部分是max(0, h[i] - H)，求 H 最大能设多高。

第一步，确定判定函数。对于给定的 H，能得到的木材总量是sum(max(0, h[i] - H))。H 越高，锯掉的越少，总量越小；H 越低，总量越大。这是一个单调递减关系。

第二步，确定二分方向。我们要找的是"满足总量 >= m 的最大的 H"，属于求最大可行值，用上取整模板。

第三步，确定上下界。下界取 0（锯片贴地面，木材最多），上界取max(h[i])（超过最高树就一根木材都拿不到）。注意上界不能随便取个 1e18，那样虽然二分还能跑，但 mid 会超出 int 范围导致溢出。

bool check(vector<int>& h, long long m, int H) { long long total = 0; for (int x : h) { if (x > H) total += x - H; if (total >= m) return true; // 提前退出，避免累加溢出 } return total >= m; } int solve(vector<int>& h, long long m) { int l = 0, r = *max_element(h.begin(), h.end()); while (l < r) { int mid = l + (r - l + 1) / 2; // 上取整 if (check(h, m, mid)) l = mid; else r = mid - 1; } return l; }

第四步，检查细节。total用long long是必须的，n 和 h[i] 都到 1e6 级别的时候，累加结果能到 1e12，int 直接爆。check里加一句提前返回也是好习惯，既能防溢出，又能让不可行的分支早退。

实测下来，这道题的主要坑就两个：一个是没开long long，另一个是上界取成了一个固定的大数导致 mid 溢出。这两个问题在提交记录里出现的频率高得离谱。

6. 变体场景：旋转数组和峰值查找怎么套同一套框架

6.1 旋转有序数组：先判断哪半边是有序的

旋转数组的题目是"一个升序数组在某个位置被旋转过，比如 [4,5,6,7,0,1,2]，要求在 O(log n) 时间内查找目标值"。整体不有序，但可以二分，因为任意切一刀，至少有一半是有序的。

思路是这样：取mid之后，拿nums[mid]和nums[l]比。如果nums[mid] >= nums[l]，说明[l, mid]这一段是升序的（没被旋转点切断）；否则说明[mid, r]这一段是升序的。判断出哪边有序之后，再看目标值是否落在有序那半边的数值区间里，落在里面就往那边收缩，否则去另一边。

int search(vector<int>& nums, int target) { int l = 0, r = (int)nums.size() - 1; while (l <= r) { int mid = l + (r - l) / 2; if (nums[mid] == target) return mid; if (nums[mid] >= nums[l]) { // 左半段有序 if (target >= nums[l] && target < nums[mid]) { r = mid - 1; } else { l = mid + 1; } } else { // 右半段有序 if (target > nums[mid] && target <= nums[r]) { l = mid + 1; } else { r = mid - 1; } } } return -1; }

这里的nums[mid] >= nums[l]用大于等于而不是严格大于，是有原因的：当区间只剩两个元素时l和mid会重合，此时nums[mid] == nums[l]，应该归到"左半段有序"这一类（左半段只有一个元素，当然有序）。如果写成严格大于，这种情况就会走进另一个分支，逻辑就乱了。

6.2 寻找峰值：把比较对象从两端换成 mid 和 mid+1

"寻找峰值"这道题（数组中没有相邻相等的元素，要求找出任意一个峰值的位置，要求 O(log n)）是二分变体里的另一颗明星。它的判定条件设计得非常巧妙：比较nums[mid]和nums[mid+1]。

如果nums[mid] < nums[mid+1]，说明从 mid 到 mid+1 是在上升，那么峰值一定在 mid 的右边（因为数组两端可以视为负无穷，上升趋势最终一定会掉头向下，掉头的那个点就是峰）。反之如果nums[mid] > nums[mid+1]，说明在下降，峰值要么是 mid 自己，要么在 mid 左边。

int findPeakElement(vector<int>& nums) { int l = 0, r = (int)nums.size() - 1; while (l < r) { int mid = l + (r - l) / 2; if (nums[mid] < nums[mid + 1]) { l = mid + 1; // 上升，峰在右边 } else { r = mid; // 下降或持平，峰在左边（含 mid） } } return l; // 区间收敛到唯一元素，即峰值下标 }

这段代码里有个安全细节值得说：nums[mid + 1]会不会越界？答案是不会，因为循环条件是l < r，所以mid = (l + r) / 2 < r <= n - 1，那么mid + 1 <= n - 1，访问一定在数组范围内。这种"通过循环条件反推访问是否越界"的分析方式，是写二分变体时必须养成的习惯，比写完再靠运行时报错来找安全得多。

7. 我的二分调试清单和几条踩坑之外的感悟

7.1 交卷前必查的六件事

写了这么多年的二分，我给自己总结了一份固定清单，每次写完不管多有信心都会过一遍。第一件是区间定义写清楚——[l, r]还是[l, r)，这个决定了循环条件和所有更新的形式，定义搞混了后面全错。第二件是循环条件与区间定义匹配，闭区间是l <= r，左闭右开是l < r。第三件是mid的取整方向和更新方式配对，这条已经在第 3 章说透了。

第四件是防止加法溢出，永远写l + (r - l) / 2，不要写(l + r) / 2。当l和r都是 1e9 量级时，l + r会直接溢出成负数，mid变成垃圾值，程序行为不可预测。这个问题在本地小数据上完全测不出来，交上去遇到大数据才炸，非常隐蔽。

第五件是check函数的单调性验证。二分答案的check如果方向写反了，程序不会报错，只会安静地给出错误答案。我的做法是手工构造几个小例子，把check在几个不同参数下的返回值打印出来，肉眼确认单调性确实成立。

第六件是边界用例，也就是 3.2 节那四种场景，空数组、单元素、全满足、全不满足。这四条能挡掉绝大多数隐藏 bug。

7.2 几个不写在教科书里的经验

第一个经验是关于学习的顺序。我不建议一开始就去背lower_bound和upper_bound的实现，那样只会记住形状不理解原因。正确的顺序是先能用闭区间模板写对最朴素的有序数组查找，再理解为什么找边界时需要左闭右开，最后才是用标准库函数替换自己的实现。跳过中间步骤直接背库函数的人，遇到变形题基本就废了。

第二个经验是关于练习量的。二分这个东西，看十遍不如自己写三遍，而且写的时候必须关掉题解。我的建议是去找十道二分题，其中三题是纯查找、三题是找边界、四题是二分答案，全部闭卷写，写完对拍。走完这一轮，二分就不会再是问题了。

第三个经验是关于"一写就会"这件事的真相。所谓一写就会，不是指凭空写对，而是指建立了一套机械化的检查流程，写完之后按流程过一遍，能自动发现错误。这份清单就是那套流程。很多人觉得自己"会了"，其实是"看着答案能看懂"，真正的会是把错误模式都见过一遍，知道每种错误长什么样、怎么识别。

最后一个经验：不要迷信任何一种模板。我上面给的所有代码都可以正常工作，但在具体题目里，往往还有更贴合题意的写法。模板是用来建立肌肉记忆的，不是用来套的。等你把这两套模板写到手熟，自然就会在遇到新题的时候自己长出新变体来，那时候才算真的掌握了二分。

如果你现在还在为l和r纠结，不用焦虑，这东西就是这样，写错了十次之后才会突然通透，我当初也是这么过来的。挑一道最基础的题，把上面那两套模板默写一遍，再跑一次对拍，你会发现它比想象中简单。