适用对象： 已完成第 2 课（排序与贪心）的同学 使用方式： 自学讲义。例题必须自己动手写一遍，不许只看 学完本课，你应该能：
lower_bound /
upper_boundcheck
函数的思路使用说明：
| 符号 | 含义 |
|---|---|
| ⭐ | 基础题，热身 |
| ⭐⭐ | 实战题，对应复赛 T1 难度 |
| ⭐⭐⭐ | 冲刺题，对应复赛 T2 难度 |
| ⚠️ | 考场易错点 |
| 📝 | 规则/结论速记 |
上节课学的 sort
把数组排好了序。数组一旦有序，找一个数就不用从头扫到尾——每次看中间的数，能排除一半的可能性，这就是二分查找。
猜数字游戏的道理：1~100 猜一个数，每次猜中间值，对方告诉你"大了"还是"小了"，最多猜 7 次就能猜中——这就是二分。
#include <bits/stdc++.h>
using namespace std;
int main() {
int a[5] = {7, 19, 42, 42, 88}; // 必须先排好序
int x = 42;
int l = 0, r = 4, ans = -1;
while (l <= r) {
int mid = l + (r - l) / 2; // 中间下标
if (a[mid] == x) { ans = mid; break; }
else if (a[mid] < x) l = mid + 1; // 中间值太小，往右找
else r = mid - 1; // 中间值太大，往左找
}
cout << ans << endl;
return 0;
}输出：2（a[2] == 42）。把 x
改成 50 再跑一次，输出
-1——数组里没有这个数。
⚠️ mid = l + (r - l) / 2 别偷懒写成
(l + r) / 2。数值小的时候两种写法结果一样，但
l + r 在下标范围极大时可能溢出——写成
l + (r - l) / 2 是竞赛里的标准习惯，现在就养成。
📝 复杂度 O(log n)：对照第 1 课的预算表，n = 10⁸
也只要查大约 27 次，比 sort 还快一个数量级。
lower_bound / upper_bound（15
分钟）手写二分容易漏边界，STL 已经把最常用的两种二分包装好了，前提是数组必须先排序：
#include <bits/stdc++.h>
using namespace std;
int main() {
int a[5] = {7, 19, 42, 42, 88};
int pos1 = lower_bound(a, a + 5, 42) - a; // 第一个 >= 42 的下标
int pos2 = upper_bound(a, a + 5, 42) - a; // 第一个 > 42 的下标
cout << pos1 << " " << pos2 << endl;
cout << pos2 - pos1 << endl; // 42 出现的次数
return 0;
}输出：
2 4
2lower_bound/upper_bound
返回的是指针（迭代器），减去数组首地址 a
才变成下标——这是固定写法，记住就行。
📝 两个常见用途： 判断 x
在不在数组里——pos1 < n && a[pos1] == x；统计 x
出现了几次——upper_bound(...) - lower_bound(...)。
前两节二分的是数组下标。还有一大类题，二分的是答案本身——这类问题的共同特征：
答案越大，某个条件越难满足（或越容易满足）；答案越小，反过来。这种"一边全行、一边全不行，中间有个分界线"的性质叫单调性。
三步走框架：
[l, r]（通常是"最大化最小值"或"最小化最大值"里那个待求的值）check(mid) 函数：假设答案是
mid，判断这个假设是否可行check
的结果收缩边界——可行就试试更优的一边，不可行就往另一边收while (l <= r) {
long long mid = l + (r - l) / 2;
if (check(mid)) { ans = mid; l = mid + 1; } // 可行：mid 能取到，试试更大的
else r = mid - 1; // 不可行：mid 太大了
}（如果要找的是"最小化最大值"，方向反过来：check(mid)
可行就 r = mid - 1 去找更小的，不可行就
l = mid + 1。判断方向的窍门：先想清楚 check
可行时，答案该往哪边收缩。）
📝 二分答案三问： 二分的是什么？范围是什么？check 函数怎么写？
有 n 段原木，第 i 段长度 aᵢ。要把这些原木切成长度相同的小段（长度必须是正整数，允许有剩余料不用），至少要切出 k 段。求这个长度最大能是多少。
输入样例： 3 7 232 124 456 输出样例： 114（第一行 n 和 k，第二行是 n 段原木的长度；题目名
wood）
分析： 长度 L 越大，每段原木能切出的小段数
aᵢ / L（向下取整）就越少——单调性成立：L
变大，能切出的总段数只会变少或不变。所以二分 L，check(L) =
"总共能切出的段数 ≥ k 吗"。
#include <bits/stdc++.h>
using namespace std;
int n, k;
long long a[100005];
bool check(long long len) {
long long cnt = 0;
for (int i = 1; i <= n; i++) cnt += a[i] / len;
return cnt >= k;
}
int main() {
freopen("wood.in", "r", stdin);
freopen("wood.out", "w", stdout);
cin >> n >> k;
long long maxLen = 0;
for (int i = 1; i <= n; i++) {
cin >> a[i];
maxLen = max(maxLen, a[i]);
}
long long l = 1, r = maxLen, ans = 0;
while (l <= r) {
long long mid = l + (r - l) / 2;
if (check(mid)) { ans = mid; l = mid + 1; } // 切得出 k 段，试试切更长的
else r = mid - 1; // 切不出 k 段，长度太大了
}
cout << ans << endl;
return 0;
}样例验证：L=114 时，232/114=2、124/114=1、456/114=4，共 7 段，恰好够；L=115 时，232/115=2、124/115=1、456/115=3，共 6 段，不够。所以 114 是能行的最大长度 ✓
⚠️ l 从 1 开始，不能从 0 开始——a[i] / 0
会让程序直接崩溃（除以 0）。
一条长度为 L 的河道，起点和终点之间散布着 n 块石头（不含起点终点）。选手每步跳到下一块石头（或终点），直至到达终点。组委会最多可以移走 m 块石头，使得比赛过程中最短的一次跳跃距离尽可能大。求这个最大化后的最短跳跃距离。
输入样例： 25 5 2 2 11 14 17 21 输出样例： 4（第一行 L、n、m；第二行是 n 块石头到起点的距离；题目名
stone。样例说明：移走距起点 2 和 14 的两块石头后，剩下的间隔是 0→11→17→21→25，最短跳跃是 17→21 或 21→25，长度 4。）
分析： 假设"最短跳跃距离"至少是 d——d
越大，需要移走的石头就越多（因为间隔小的地方必须清空一块）。d
变大，需要移走的石头数只会变多或不变，单调性成立。二分
d，check(d) = "按贪心策略最少要移走几块，够不够 m 块"。
check 的贪心策略：
从起点开始扫描每块石头，如果它离"上一块保留的石头"距离
< d，就必须移走它（累计
removed）；否则保留它，更新"上一块保留的石头"。终点是固定不能移走的，最后也要满足间隔。
#include <bits/stdc++.h>
using namespace std;
int n, m;
long long L, pos[50005];
bool check(long long d) {
long long removed = 0, last = 0;
for (int i = 1; i <= n + 1; i++) { // n+1 是终点 L，不能被移走
if (i <= n && pos[i] - last < d) removed++;
else last = pos[i];
}
return removed <= m;
}
int main() {
freopen("stone.in", "r", stdin);
freopen("stone.out", "w", stdout);
cin >> L >> n >> m;
for (int i = 1; i <= n; i++) cin >> pos[i];
sort(pos + 1, pos + n + 1);
pos[n + 1] = L; // 终点当成一块不能移除的"石头"
long long l = 0, r = L, ans = 0;
while (l <= r) {
long long mid = l + (r - l) / 2;
if (check(mid)) { ans = mid; l = mid + 1; } // 移走的块数够，试试更大的 d
else r = mid - 1; // 移走的块数不够，d 太大了
}
cout << ans << endl;
return 0;
}样例验证：check(4)——石头依次 2,11,14,17,21，终点
25。上一块保留=0：2-0=2<4，移走(1)；11-0=11≥4，保留，last=11；14-11=3<4，移走(2)；17-11=6≥4，保留，last=17；终点
25-17=8≥4，保留。共移走 2 块，恰好等于 m，可行。check(5)
会发现至少要移走 3 块，超过 m，不可行。所以答案是 4 ✓
⚠️ 这题是"最大化最小值"，check 可行时说明 d
还能再大，l = mid + 1；这一点和木材加工是同一个方向（都是"可行就往更大试"），但不是所有二分答案题都这样，动笔前先想清楚这一点。
📝 check 函数的共同点： 假设答案是 mid，用贪心或模拟去验证一遍，看能不能满足题目要求——二分答案的难点往往不在二分本身，而在 check 怎么写。
⭐ 基础：手写二分查找练习（不用 freopen，直接输出即可）
数组 {3, 8, 15, 15, 27, 40}，分别查找
x = 15 和 x = 9，输出各自的下标（找不到输出
-1）。
#include <bits/stdc++.h>
using namespace std;
int find(int a[], int n, int x) {
int l = 0, r = n - 1, ans = -1;
while (l <= r) {
int mid = l + (r - l) / 2;
if (a[mid] == x) { ans = mid; break; }
else if (a[mid] < x) l = mid + 1;
else r = mid - 1;
}
return ans;
}
int main() {
int a[6] = {3, 8, 15, 15, 27, 40};
cout << find(a, 6, 15) << endl;
cout << find(a, 6, 9) << endl;
return 0;
}输出 2（或 3，取决于 mid 走到哪个
15，两个都算对）和 -1。把重复逻辑写成函数
find，比每次都复制一遍 while 循环干净。
⭐⭐ 实战：统计区间内有多少个数（题目名
count）
给定一个已排好序的数组（n 个数，1 ≤ n ≤ 10⁵）和一个区间
[low, high]，统计数组中有多少个数落在这个区间内（包含端点）。
输入样例：
6
2 5 5 5 8 12
3 8
输出样例：
4（区间 [3,8] 内的数是 5,5,5,8，共 4 个。）
#include <bits/stdc++.h>
using namespace std;
int main() {
freopen("count.in", "r", stdin);
freopen("count.out", "w", stdout);
int n;
cin >> n;
int a[100005];
for (int i = 0; i < n; i++) cin >> a[i];
int low, high;
cin >> low >> high;
int p1 = lower_bound(a, a + n, low) - a; // 第一个 >= low 的位置
int p2 = upper_bound(a, a + n, high) - a; // 第一个 > high 的位置
cout << p2 - p1 << endl;
return 0;
}数组已经有序，upper_bound(high) - lower_bound(low)
就是落在 [low, high] 里的个数——比一个个数快得多。
⭐⭐⭐ 冲刺：吃香蕉（经典二分答案题，题目名
banana）
有 n 堆香蕉，第 i 堆有 pᵢ 根。你要在 h 小时内吃完所有香蕉：每小时选一堆，以速度 k（根/小时）吃，这一堆够 k 根就吃 k 根，不够就把这堆吃完（这一小时不再吃别的堆）。求能在 h 小时内吃完的最小速度 k（k 为正整数）。
输入样例： 4 8 3 6 7 11 输出样例： 4
先自己想 10 分钟：这题和前两道例题的方向哪里不一样？
速度 k 越大，吃完所有香蕉花的小时数（每堆用时 ⌈pᵢ / k⌉
向上取整）就越少——这次是"求最小值"，check 可行（h
小时内吃完）时应该尝试更小的
k，r = mid - 1；不可行就
l = mid + 1。跟木材加工、跳石头刚好反过来。
#include <bits/stdc++.h>
using namespace std;
int n;
long long h, piles[10005];
bool check(long long k) {
long long hours = 0;
for (int i = 1; i <= n; i++) hours += (piles[i] + k - 1) / k; // 向上取整
return hours <= h;
}
int main() {
freopen("banana.in", "r", stdin);
freopen("banana.out", "w", stdout);
cin >> n >> h;
long long maxPile = 0;
for (int i = 1; i <= n; i++) { cin >> piles[i]; maxPile = max(maxPile, piles[i]); }
long long l = 1, r = maxPile, ans = maxPile;
while (l <= r) {
long long mid = l + (r - l) / 2;
if (check(mid)) { ans = mid; r = mid - 1; } // h 小时内吃得完，试试更慢的速度
else l = mid + 1; // 吃不完，速度太慢了
}
cout << ans << endl;
return 0;
}样例验证：k=4 时，⌈3/4⌉+⌈6/4⌉+⌈7/4⌉+⌈11/4⌉ = 1+2+2+3 = 8 小时，恰好等于 h；k=3 时算出来要 10 小时，超了。所以最小可行速度是 4 ✓
手写二分模板：
int l = 0, r = n - 1, ans = -1;
while (l <= r) {
int mid = l + (r - l) / 2;
if (a[mid] == x) { ans = mid; break; }
else if (a[mid] < x) l = mid + 1;
else r = mid - 1;
}STL 二分：
lower_bound(a, a + n, x) - a; // 第一个 >= x 的下标
upper_bound(a, a + n, x) - a; // 第一个 > x 的下标二分答案框架：
while (l <= r) {
long long mid = l + (r - l) / 2;
if (check(mid)) { ans = mid; l = mid + 1; } // 求最大值：可行就试更大
else r = mid - 1;
}（求最小值方向相反：可行就
ans = mid; r = mid - 1;，不可行
l = mid + 1;）
二分答案三问： 二分的是什么？范围是什么？check 函数怎么写（通常是贪心或模拟）？
易错点：
| 写法 | 问题 |
|---|---|
(l + r) / 2 |
应写成 l + (r - l) / 2，养成不溢出的习惯 |
l 从 0 开始做除法二分 |
除以 0 会崩溃，下界至少从 1 开始 |
| 二分方向搞反 | 动笔前先想清楚 check 可行时答案该往哪边收缩 |
lower_bound/upper_bound
统计区间个数的写法能脱稿写出来