二分的思想你早就会了 —— 猜数字游戏，猜大了往小猜，猜小了往大猜。三句话说完。
但二分是竞赛里最容易写错的算法，没有之一。错法五花八门： 死循环、少算一个、多算一个、越界。而且这些错误常常能过样例， 在大数据上才发作。
所以这一章不追求「讲清楚思想」，追求的是： 让你从此以后，写二分不再靠试。
办法是只学一个模板，然后把它焊死在肌肉记忆里。
1 一句话问题
给一个从小到大排好序的数组（可以有重复），q 次询问，每次给一个 x，回答三件事：
L = 第一个 >= x 的位置 （都比 x 小就输出 n+1）
U = 第一个 > x 的位置 （都不比 x 大就输出 n+1）
C = x 出现了几次输入 8 3
1 3 3 4 4 4 7 9
4 L=4（a[4]=4 是第一个 ≥4 的）U=7（a[7]=7）C=3
5 L=7 U=7 C=0（5 不存在）
100 L=9 U=9 C=0（比谁都大，落到 n+1）
输出 4 7 3
7 7 0
9 9 0因为它们是二分查找的三种最常见需求，而且有个漂亮的关系：
C = U - L。
「x 出现了几次」根本不用单独写代码 —— 两个二分一减就出来了。
这三个量在 C++ 标准库里就叫 lower_bound、upper_bound，
名字值得记住，第 7 步会用到。
2 先用纸笔手算一遍
拿 1 3 3 4 4 4 7 9 找 x = 4：
位置: 1 2 3 4 5 6 7 8 (9)
值: 1 3 3 4 4 4 7 9 ∞
↑ ↑
L=4 U=7注意最右边那个虚构的位置 9（也就是 n+1）。它不存在于数组里，
但必须把它算成候选：当 x = 100 时，答案就落在那儿。
我们要找的不是「等于 x 的位置」，而是**「分界线」**：
小于 x 的一段 | >= x 的一段
1 3 3 | 4 4 4 7 9 ∞
↑
这条线的位置就是 L数组被 x 切成两半：左边全是「不满足」，右边全是「满足」。
二分要找的就是这条分界线。
这个视角非常重要，因为它把「找一个数」变成了「找一个分界点」—— 而分界点一定存在（哪怕在最左边或最右边），不需要特判「找不到」。 第 9 章的二分答案，用的就是这个视角。
3 暴力：从头一个个看
点「运行 ▶」看结果
O(n) 一次询问。它慢，但它是那三个定义最诚实的表述 —— 待会儿拿它当标准答案。
4 实测：它有多慢
本机实测：
| n = q | 线性扫描 O(n·q) | 二分 O(q log n) |
|---|---|---|
| 20 000 | 0.20 秒 | 0.01 秒 |
| 50 000 | 1.32 秒 | 0.02 秒 |
| 100 000 | 5.21 秒 | 0.04 秒 |
| n | log₂n（大约要几轮） |
|---|---|
| 1 000 | 10 |
| 1 000 000 | 20 |
| 1 000 000 000 | 30 |
数据规模从一千涨到十亿（一百万倍），二分只从 10 轮变成 30 轮。
这就是为什么「能二分就二分」—— 它几乎是免费的。
5 ★ 关键的一步：只学一个模板
int l = 1, r = n + 1; // 候选范围 [l, r]，多留 n+1 那一格表示「找不到」
while (l < r) {
int mid = l + (r - l) / 2;
if (check(mid)) r = mid; // mid 满足 → 答案在 [l, mid]，mid 自己也算候选
else l = mid + 1; // mid 不满足 → 答案在 [mid+1, r]，mid 被淘汰
}
// 出来时 l == r，就是答案这一章只有这一个模板。所有变化都只是换 check：
找第一个 >= x → check(mid) 是 a[mid] >= x
找第一个 > x → check(mid) 是 a[mid] > x写的时候不要背口诀，只问自己一句话：
「mid 满足条件的时候，答案还可能在 mid 右边吗？」
不可能 →
r = mid（mid 得留着，它可能就是答案） 可能 →l = mid + 1（mid 没用了，扔掉）
三个细节，每一个都能让你 WA：
l == r 时区间里只剩一个数，它已经是答案了。再进循环就可能原地打转。
（l <= r 的写法也有正确版本，但它要配 r = mid - 1 和一个额外的 ans 变量。
两套模板混着记 = 一定写错。这一章只认上面那一个。）
因为 mid 是下取整的。当区间只剩两个数（比如 l=3, r=4）时：
mid = 3 + (4 - 3) / 2 = 3 ← mid 等于 l如果这时走的分支是 l = mid，那 l 还是 3，r 还是 4，区间一点都没缩小 ——
下一轮 mid 还是 3，永远循环下去。
下一步就让你亲眼看它死给你看。
l + r 在两者都接近 int 上限时会溢出成负数，然后数组访问越界。
本章的数据不会触发，但这是个免费的好习惯 —— 打字就多两个字符。
6 亲眼看一次死循环
点「运行 ▶」看结果
输出会是这样：
第 1 轮：l = 1, r = 6, mid = 3
第 2 轮：l = 3, r = 6, mid = 4
第 3 轮：l = 3, r = 4, mid = 3
第 4 轮：l = 3, r = 4, mid = 3 ← 和上一轮一模一样
第 5 轮：l = 3, r = 4, mid = 3 ← 还是一模一样
...拿「区间只剩两个数」代进去，手动走一轮。
只要有任何一个分支让区间没缩小，就是死循环。
这个检查花不了十秒钟，但它能挡住二分 90% 的翻车。 比赛的时候尤其值得做 —— 死循环意味着这道题 0 分， 而且你在考场上很难意识到「它不是慢，是根本停不下来」。
如果把 mid 改成上取整：
int mid = l + (r - l + 1) / 2;那么配 l = mid / r = mid - 1 就是对的（这是「找最后一个满足条件的位置」常用的写法）。
关键是：mid 的取整方向和分支的写法必须配套，不能混搭。 记不住就只用第 5 步那一个模板 —— 它能解决这一章和第 9 章的全部问题。
7 正解 + 标准库的写法
点「运行 ▶」看结果
两个函数长得几乎一模一样，唯一的区别是 >= 和 >。这就是模板的价值。
C++ 标准库早就把它们写好了：
点「运行 ▶」看结果
两个理由：
- 第 9 章的二分答案根本没有数组给你
lower_bound。 那里二分的是「答案本身」，check是一个自己写的函数。手写模板必须会。 lower_bound用在set/map上会退化成 O(n) —— 它们不是连续存储的。那两个容器要用自己的成员函数s.lower_bound(x)。
比赛里能用 STL 就用（少写十行少十个错），但模板要能默写。
8 单步看区间怎么减半
盯住两件事：
- 蓝色的候选区间每一轮恰好少一半，一次都没有例外。
- 最右边那个虚线的
∞就是n+1。把 x 改成100播一遍 —— 它最后收敛到那一格。这就是模板里r初值必须是n+1而不是n的原因。
然后切到「第一个 > x」再看一遍：整个过程只有一个符号变了，>= 变成 >。
数组里有三个 4，两种模式的落点正好把它们夹在中间。
点「运行 ▶」看结果
9 ★ 对拍验证
把「二分」那一栏换成你自己默写的，再点开始。
值得故意写错的，每一个都是真实高频错误：
r的初值写成n→ 「答案是 n+1」那种情况永远算不出来l = mid（少了 +1） → 死循环（对拍会报「超时」）while (l <= r)→ 死循环lowerPos里的>=写成>→ 变成了 upper，重复元素时才会暴露 —— 这就是为什么生成器一定要造重复元素mid = (l + r) / 2→ 本题不会炸，但记住它有溢出风险
如果数组里所有元素互不相同，那么 lower 和 upper 只差 1，
把 >= 写成 > 的错误几乎抓不住。
所以生成器把取值压到只有 0~8 —— n=12 的数组里必然有大量重复。 造数据的原则（第 1 章就说过）：让「错误的直觉」在你的数据上必定失败。
10 二分的适用条件
课本上说「二分用于有序数组」，这句话太窄了。真正的条件是：
存在一个分界点，左边全部不满足，右边全部满足（或者反过来）。
不满足 不满足 不满足 | 满足 满足 满足 满足
↑
分界点有序数组 + 「>= x」这个条件，恰好满足上面这个形状。 但很多题里根本没有数组 —— 只要「答案越大越容易满足」，就能二分。
那就是下一章的全部内容。
11 自测
- 洛谷 P2249 查找 —— lower_bound 模板题。先手写一遍，再用 STL 写一遍，对比结果
- 洛谷 P1102 A-B 数对 —— 上一章用双指针做过，现在用「排序 + 两次二分」再做一遍 —— 这题正好是 U-L 的用武之地
- 洛谷 P1873 砍树 —— 二分答案。做不出来很正常，下一章就讲它 —— 但可以先自己试试
- 洛谷 P1024 一元三次方程求解 —— NOIP2001。实数二分，注意精度和循环终止条件（不能用 l < r）
第 9 章二分答案，是二分真正的杀手锏，也是 CSP-J/S 的高频考点。
它的套路很反直觉：不会直接求答案？那就猜一个，再写个函数验证这个猜测行不行。 而「验证」通常比「求解」简单一百倍。
这一章的模板会原封不动地用上，只是 check 从「比大小」变成「一段贪心」。