Lesson 0414 · 二分：二分查找与二分答案

④ 数据结构与算法 — 第 14 课

1. 二分查找：在有序数组里找位置

先看最基础的问题：数组 a 单调不减，要找出第一个大于等于 x 的位置。

暴力是扫一遍 O(n)；二分是每次看中间那个数，跟 x 比一下，砍掉一半，O(log n)。n = 10⁶ 时，扫一遍要 10⁶ 次，二分只要 20 次。

int lowerBound(const vector<int>& a, int x) {   // 第一个 >= x 的下标；都不满足返回 n
    int l = 0, r = (int)a.size();              // 左闭右开 [l, r)
    while (l < r) {
        int mid = l + (r - l) / 2;
        if (a[mid] >= x) r = mid;              // mid 可能就是答案，别丢
        else l = mid + 1;                      // mid 肯定不是，跳过
    }
    return l;
}

三个常用变体

P2249 要的就是「第一个 ≥ x」，然后再检查 a[pos] == x：相等说明找到了，输出 pos + 1（题面是 1-based）；否则输出 -1。

实测（数组 1 3 3 3 5 7）：

P2249 查 3 → 2
P2249 查 6 → -1

死循环是怎么来的

二分最常见的 bug 不是答案错，是死循环。看这个错误写法（求「最后一个满足条件的」时很多人这么写）：

while (l < r) {
    int mid = (l + r) / 2;      // 下取整
    if (ok(mid)) l = mid;       // ← 问题在这：l 可能等于 mid，永远不前进
    else r = mid - 1;
}

l = 5, r = 6 时 mid = (5+6)/2 = 5，l = mid = 5 什么都没变。修法是 mid 上取整：

int mid = (l + r + 1) / 2;      // 或者 l + (r - l + 1) / 2

2. 二分答案：把「求最优」换成「判对错」

这是二分的第二个用法，也是比赛里更常见的那个。它解决的问题长这样：

• 「分成 M 段，使每段和的最大值最小」 —— P1182
• 「移走 M 块石头，使最短跳跃距离最大」 —— P2678
• 「最少要多大的一组桶，才能在 T 天内运完」 —— 各种变形题

这些题直接做很难：你怎么知道最优的分法长什么样？但反过来问就简单多了 —— 「如果答案是 x，能不能做到？」 这个判断往往一遍贪心就够了。

两套模板

// ① 求「最小可行值」：可行就往下压
long long l = low, r = high;
while (l < r) {
    long long mid = l + (r - l) / 2;        // 下取整
    if (check(mid)) r = mid;                // 可行 → 答案不会比 mid 大
    else l = mid + 1;
}
// 结束时 l == r 就是答案

// ② 求「最大可行值」：可行就往上推
long long l = low, r = high;
while (l < r) {
    long long mid = l + (r - l + 1) / 2;    // 上取整，别忘
    if (check(mid)) l = mid;
    else r = mid - 1;
}

两套只差三处：区间的移动方向、mid 的取整、以及最后取 l 还是 r（其实一样，因为循环结束时它们相等）。写之前先想清楚：我要的是「最小」还是「最大」 —— 想错了就是死循环或差一。

3. P1182 数列分段：check 就是「贪心分段」

把它换成判断题：

bool check(long long x) {
    int cnt = 1;                 // 至少一段
    long long sum = 0;
    for (long long v : a) {
        if (v > x) return false; // 单个元素都比 x 大，一段装不下
        if (sum + v <= x) sum += v;
        else { cnt++; sum = v; }
    }
    return cnt <= m;
}

二分的区间：lo = max(a)（每段至少装一个数），hi = sum(a)（一段装完）。

样例逐轮推演（a = 4 2 4 5 1，分 3 段）

四轮之后 lo = hi = 6，答案 6。注意第 3 轮：check(6) 说「3 段刚好够」，于是把上界压到 6；第 4 轮 check(5) 就要 5 段了，说明 5 不行。

实测（N = 10⁵、M = 30000 的随机数据）：3.7 ms；另外 150 组随机小数据与暴力枚举所有切分方式对拍，0 组不一致。

4. P2678 跳石头：check 是「贪心搬石头」

判断题：check(x)：能不能通过搬走 ≤ M 块石头，让每一跳都不少于 x？

贪心：从起点出发，能跳到 x 远就跳；跳不过去就把这块石头搬走。最后别忘检查最后一跳。

bool check(long long x) {
    int cnt = 0;             // 搬走了几块
    long long last = 0;      // 上一块「保留下来」的石头位置
    for (int i = 1; i <= n; i++) {
        if (d[i] - last < x) cnt++;      // 距上一块太近 → 搬走它
        else last = d[i];                // 够远 → 保留，作为新的落脚点
    }
    if (L - last < x) cnt++;             // 最后一跳不够 → 把最后保留的那块也搬走
    return cnt <= m;
}

样例逐轮推演（L = 25，石头 2 11 14 17 21，最多搬 2 块）

四轮后 lo = hi = 4，答案 4。注意这里 mid 是上取整（(l + r + 1) / 2），因为要求的是「最大可行值」。

实测（L = 10⁹、N = 50000、M = 10000 的随机数据）：1.9 ms。

5. 什么时候该想到二分答案

看到下面这些字眼，先问自己「能不能二分」：

和前面几课的关系：check 里面往往就是前几课的东西 —— P1182 的 check 是贪心，P2678 的 check 也是贪心，有些题（比如「二分 + 判连通」）的 check 会用到并查集或 BFS。二分本身很简单，难点永远在 check。

实测汇总

6. 坑点清单

• mid 的取整方向：l = mid 配上取整，r = mid 配下取整；错了就是死循环
• mid = l + (r - l) / 2 而不是 (l + r) / 2：后者在 l + r 超过 int 时会溢出
• 区间初始化：二分答案的 lo / hi 必须是「一定不可行 / 一定可行」或者「一定可行 / 一定不可行」，想清楚哪头是哪头
• check 里的边界值：P1182 的 if (v > x) return false; 不能省（单个元素比 x 还大时，一段装不下）
• check 忘记处理末尾：P2678 最后那一跳（L - last）最容易漏
• 答案范围用 long long：P1182 的答案能到 10⁹ 级、P2678 的 L 也是 10⁹
• 二分查找要先确认数组有序：题目说「单调不减」，别自己再排一遍（P2249 的输入本来就是有序的）
• 找到之后还要判等：lower_bound 只保证「第一个 ≥ x」，那个位置上的值可能不是 x（P2249 要输出 -1）

7. 小测

8. 动手练习

1. P2249 查找（先写这题）—— n ≤ 10⁶、m ≤ 10⁵，输入输出量大，记得 ios::sync_with_stdio(false); cin.tie(nullptr);。用你手写的 lowerBound 交一次，再用 std::lower_bound 交一次，看两者有没有差别。
2. P1182 数列分段 —— 二分答案入门。先想清楚 lo 和 hi 各该取什么，再写 check。
3. P2678 跳石头 —— 和 P1182 是同一个套路，难的只有 check 里末尾那一跳。写完自己造两组数据：一组「石头很密」、一组「M = 0」。

本课小结

• 二分的前提是单调：能砍掉一半，靠的是「这一半里肯定没有答案」
• 二分查找：lowerBound 求「第一个 ≥ x」，找到后还要判等（P2249 的 -1）
• 死循环的根源：l = mid 配下取整 → mid 必须上取整；r = mid 配下取整
• 二分答案：把「最大值最小 / 最小值最大」换成「判 x 行不行」+ 两套模板
• 难点在 check：P1182 是贪心分段，P2678 是贪心搬石头；check 里常常要用到前面几课的东西
• 我的真实错误：P2678 末尾写成 return false，应该 cnt++；对拍 200 组才抓出来
• 实测：P2249 13.8 ms、P1182 3.7 ms、P2678 1.9 ms，全部远在时限内