二分搜索

前言

你玩过猜数字游戏吗？“我想了一个 1 到 100 之间的数，你来猜。“如果你从 1 开始一个个试，最坏要猜 100 次。但如果你每次猜中间的数——先猜 50，“大了”，再猜 25，“小了”，再猜 37……最多只需要 $\log_2(100) \approx 7$ 次。

这就是二分搜索。它不只用于”在排序数组里找某个数”。更准确地说，任何可以二分答案空间的问题，都可以用二分。后面你会看到，很多时候我们甚至不是在数组中搜索，而是在二分”答案本身”。

问题的本质

二分搜索的核心前提是单调性：如果某个值 $x$ 满足条件，那么所有 $\ge x$（或 $\le x$）的值也满足。

举个例子：“数组中第一个 $\ge \text{target}$ 的位置”。如果 $a[5] \ge \text{target}$，那 $a[6], a[7], \ldots$ 也 $\ge \text{target}$（因为数组已排序）。这个单调性让我们可以每次把搜索空间砍一半——如果 $a[\text{mid}] \ge \text{target}$，答案在左半（含 mid）；否则答案在右半（不含 mid）。

理论 + 代码

标准 lower_bound：找第一个 $\ge \text{target}$ 的位置

int lower_bound(int a[], int n, int target) {
    int lo = 0, hi = n;                  // ① 搜索范围 [lo, hi)
    while (lo < hi) {                    // ② 当范围不为空
        int mid = lo + (hi - lo) / 2;    // ③ 中点
        if (a[mid] < target)
            lo = mid + 1;                // ④ mid 不够大，答案在右半
        else
            hi = mid;                    // ⑤ mid 可能是答案，保留
    }
    return lo;                           // ⑥ lo == hi，就是答案
}

• ① 搜索范围是 $[\text{lo}, \text{hi})$——左闭右开。lo = 0, hi = n 表示”整个数组”。
• ③ lo + (hi - lo) / 2 而不是 (lo + hi) / 2——因为 lo + hi 可能溢出 int。
• ⑤ hi = mid 而不是 hi = mid - 1——因为 mid 可能就是答案，不能排除。

走一遍过程：在 [1, 3, 5, 7, 9] 中找第一个 $\ge 4$ 的位置。

步骤	lo	hi	mid	a[mid]	判断	新范围
1	0	5	2	5	$5 \ge 4$，hi=2	[0,2)
2	0	2	1	3	$3 < 4$，lo=2	[2,2)

lo == hi == 2，答案是位置 2，即 a[2] = 5。手动验证：[1, 3, 5, 7, 9] 中第一个 $\ge 4$ 的确实是 5。✓

二分答案

很多时候我们不是在数组中搜索，而是二分答案本身。比如”最小的 $x$ 使得某条件成立”——对 $x$ 做二分，每次检查条件是否成立。

long long lo = 0, hi = 1e18;   // 答案范围
while (lo < hi) {
    long long mid = lo + (hi - lo) / 2;
    if (check(mid))             // ① mid 满足条件
        hi = mid;                // ② 答案在 [lo, mid] 中
    else
        lo = mid + 1;            // ③ 答案在 [mid+1, hi] 中
}
// lo 就是答案

• ① check(mid) 是一个判断”mid 是否可行”的函数。
• ② 如果可行，mid 可能就是答案，也可能还能更小，所以保留 mid。
• ③ 如果不可行，mid 太小了，答案一定比 mid 大。

坐标压缩

有时候数据值域很大（比如 $A_i$ 高达 $10^9$），但数据量不大（$N \le 10^5$）。这种情况下，我们只关心数据之间的大小关系，不关心具体值。坐标压缩就是把原始值映射成它在排序后的排名：

比如 $A = [46, 80, 11, 77, 46]$：

1. 排序去重得到 $B = [11, 46, 77, 80]$
2. 对每个 $A_i$，在 $B$ 中 lower_bound 找到它的位置（从 1 开始）：$46 \to 2, 80 \to 4, 11 \to 1, 77 \to 3, 46 \to 2$
3. 压缩结果：$[2, 4, 1, 3, 2]$

#include <algorithm>
using namespace std;

// 坐标压缩：把 a[0..n-1] 映射到 1~m（m 是不同值的个数）
void compress(long long a[], int n) {
    long long b[100010];
    for (int i = 0; i < n; i++) b[i] = a[i];
    sort(b, b + n);                              // ① 排序
    int m = unique(b, b + n) - b;                 // ② 去重
    for (int i = 0; i < n; i++)
        a[i] = lower_bound(b, b + m, a[i]) - b + 1;  // ③ 求排名（1-indexed）
}

• ② unique 把相邻的重复元素移到末尾，返回去重后的末尾指针。前提是数组已排序。
• ③ lower_bound(b, b+m, a[i]) - b 得到 $a_i$ 在排序去重数组中的下标（0-indexed），加 1 变成排名。比如 $b = [11, 46, 77, 80]$，lower_bound(b, b+4, 46) 指向 $b[1]$，所以 $46 \to 1 + 1 = 2$。

坐标压缩在后面会频繁用到——比如 03-04 树状数组 处理大值域时需要先压缩。

例题

例题 1：M&A 032 — Binary Search（★2）

题目：给定长度为 $N$ 的数组 $A$ 和一个整数 $X$。判断 $X$ 是否存在于数组 $A$ 中。存在输出 Yes，否则输出 No。

数据范围：$1 \le N \le 10^5$，$1 \le X, A_i \le 10^9$

—— AtCoder M&A 032

思路：如果用线性搜索逐个检查，$O(N)$ 也可以过（$10^5$）。但二分搜索只需 $O(\log N)$。先排序（$O(N \log N)$），然后对有序数组做二分查找。

代码：

#include <cstdio>
#include <algorithm>
using namespace std;

int main() {
    int N, X;
    scanf("%d%d", &N, &X);
    int A[100010];
    for (int i = 0; i < N; i++)
        scanf("%d", &A[i]);

    sort(A, A + N);    // ① 先排序

    // ② 二分查找：找到第一个 >= X 的位置
    int pos = lower_bound(A, A + N, X) - A;

    if (pos < N && A[pos] == X)    // ③ 检查该位置的值是否恰好等于 X
        printf("Yes\n");
    else
        printf("No\n");
}

逐行解析：

• ① 排序后才能用二分搜索。如果题目保证数组有序，就不需要这步。
• ② lower_bound(A, A + N, X) 返回指向第一个 $\ge X$ 的元素的指针。减去 A 得到下标。
• ③ lower_bound 找的是 $\ge X$，不一定是 $= X$。所以要检查 A[pos] == X。

---

例题 2：Tessoku Book — A11 Binary Search 1

题目：给定已排序的数组 $A$（$A_1 < A_2 < \cdots < A_N$）和整数 $X$。已知 $X$ 一定存在于 $A$ 中，输出 $X$ 是第几个元素（1-indexed）。

数据范围：$1 \le N \le 100000$，$1 \le A_i \le 10^9$

—— AtCoder Tessoku Book A11

思路：数组已有序，直接二分查找。和例题 1 类似，但题目保证 $X$ 存在，所以 lower_bound 的结果一定就是答案。

代码：

#include <cstdio>
#include <algorithm>
using namespace std;

int main() {
    int N, X;
    scanf("%d%d", &N, &X);
    int A[100010];
    for (int i = 0; i < N; i++)
        scanf("%d", &A[i]);

    // ① 二分查找 X 的位置（1-indexed）
    int pos = lower_bound(A, A + N, X) - A;
    printf("%d\n", pos + 1);    // ② 转为 1-indexed
}

逐行解析：

• ① lower_bound 返回第一个 $\ge X$ 的位置。因为 $X$ 一定存在且数组严格递增，lower_bound 精确定位到 $X$。
• ② AtCoder 用 1-indexed，所以 pos + 1。

---

例题 3：Tessoku Book — A12 Printer

题目：$N$ 台打印机，第 $i$ 台每隔 $A_i$ 秒印一张传单（即在 $A_i, 2A_i, 3A_i, \ldots$ 秒各印一张）。所有打印机同时启动，第 $K$ 张传单是什么时候印出来的？

数据范围：$1 \le N \le 10^5$，$1 \le K \le 10^9$，$1 \le A_i \le 10^9$

—— AtCoder Tessoku Book A12

思路：经典二分答案。问”第 $K$ 张什么时候印出”——如果假设答案是时间 $t$，那么在 $t$ 秒内第 $i$ 台打印机印了 $\lfloor t / A_i \rfloor$ 张。如果总张数 $\ge K$，说明 $t$ 可能大了或刚好；如果 $< K$，说明 $t$ 不够。

二分搜索 $t$ 的范围：最小 0，最大 $K \times \max(A_i)$（最坏情况只有一台最快的在印）。但题目保证答案 $\le 10^9$。

代码：

#include <cstdio>
using namespace std;

int main() {
    int N;
    long long K;
    scanf("%d%lld", &N, &K);
    long long A[100010];
    for (int i = 0; i < N; i++)
        scanf("%%lld", &A[i]);

    // ① 二分答案：t 秒内能否印够 K 张
    long long lo = 0, hi = 1000000000LL;
    while (hi - lo > 1) {
        long long mid = (lo + hi) / 2;
        long long cnt = 0;
        for (int i = 0; i < N; i++)
            cnt += mid / A[i];    // ② 第 i 台在 mid 秒内印了多少张
        if (cnt >= K)    // ③ 印够了，答案可能更小
            hi = mid;
        else            // ④ 不够，答案更大
            lo = mid;
    }
    printf("%lld\n", hi);
}

逐行解析：

• ① lo 是”不够”的边界，hi 是”够”的边界。循环结束时 hi 就是最小的”够”的时间。
• ② $\lfloor mid / A_i \rfloor$：第 $i$ 台在 $mid$ 秒内印了多少张。
• ③④ 标准二分答案模式：如果够了就缩小上界，不够就增大下界。

---

例题 4：T90 001 — Yokan Party（★4）

题目：长度为 $L$ 的羊羹上有 $N$ 个切口（位置 $A_1 < A_2 < \cdots < A_N$）。选 $K$ 个切口把羊羹分成 $K+1$ 段，使得最短的那段尽可能长。输出最短段的最大可能长度。

数据范围：$1 \le K \le N \le 10^5$，$1 \le L \le 10^9$

—— AtCoder Typical 90 001

思路：二分答案的典型题。设答案为 $x$——问”能否让每段长度都 $\ge x$“。如果能，$x$ 还可以更大；如果不能，$x$ 必须更小。

判定函数：从左到右贪心切。累计长度，只要当前段 $\ge x$ 就切一刀。最后看能否切出 $\ge K+1$ 段。

代码：

#include <cstdio>
using namespace std;

int main() {
    int N, L, K;
    scanf("%d%d", &N, &L);
    scanf("%d", &K);
    int A[100010];
    for (int i = 0; i < N; i++)
        scanf("%d", &A[i]);

    // ① 二分答案：每段至少 x 厘米
    int lo = 1, hi = L;
    while (hi - lo > 1) {
        int mid = (lo + hi) / 2;
        int cnt = 0, prev = 0;    // ② 切了几刀，上一个切点
        for (int i = 0; i < N; i++) {
            if (A[i] - prev >= mid) {    // ③ 当前段 >= mid，可以切
                cnt++;
                prev = A[i];
            }
        }
        // ④ 检查最后一段（从最后一个切点到右端）
        if (L - prev >= mid)
            cnt++;    // 最后一段也算

        if (cnt >= K + 1)    // ⑤ 能切出 K+1 段
            lo = mid;
        else
            hi = mid;
    }
    printf("%d\n", lo);
}

逐行解析：

• ③ 从左到右贪心：只要当前段长度 $\ge mid$，就立刻切。贪心是对的——切得越早，后面留给其他段的空间越大。
• ⑤ 能切出 $K+1$ 段说明 $mid$ 可行，尝试更大的值。

---

参考文献

教材讲解 — 競技プログラミングの鉄則 第 3 章

• 3.1 B11 Binary Search 2（sort + lower_bound 解说）
• 3.2 B12 Equation（浮点二分探索 解说）

基础练习 — アルゴリズムと数学 演習問題集

• 032 Binary Search（基础二分查找）【例题】

系统练习 — 競技プログラミングの鉄則

• A11 Binary Search 1（二分搜索）【例题】
• A12 Printer（二分答案）【例题】
• A77 Yokan Party（二分答案，同T90 001）

实战练习 — 競プロ典型 90 問

• 001 Yokan Party（★4，二分答案）【例题】

---

系列索引

第零章 基础工具

• 00-01 复杂度与暴力枚举
• 00-02 排序
• 00-03 累积和与差分

第一章 搜索技术

• 01-01 二分搜索
• 01-02 双指针与尺取法

第二章 数学基础

• 02-01 整数与整除
• 02-02 素数与筛法
• 02-03 同余与模运算
• 02-04 快速幂与逆元
• 02-05 组合计数
• 02-06 容斥原理
• 02-07 欧拉函数
• 02-08 博弈论基础

第三章 数据结构

• 03-01 栈、队列与单调栈
• 03-02 堆与优先队列
• 03-03 并查集
• 03-04 树状数组
• 03-05 线段树
• 03-06 懒标记线段树
• 03-07 Sparse Table 与倍增
• 03-08 字符串哈希

第四章 图论

• 04-01 图的遍历
• 04-02 最短路—Dijkstra 与 01-BFS
• 04-03 最短路—Bellman-Ford 与 Floyd
• 04-04 拓扑排序
• 04-05 最小生成树
• 04-06 强连通分量与 2-SAT
• 04-07 二分图与网络流
• 04-08 树上问题

第五章 动态规划

• 05-01 DP入门—状态与转移
• 05-02 背包问题族
• 05-03 LIS、LCS与编辑距离
• 05-04 区间DP
• 05-05 状态压缩DP
• 05-06 树形DP与数位DP
• 05-07 矩阵快速幂与线性递推

第六章 贪心

• 06-01 贪心策略与交换论证
• 06-02 区间调度与优化

第七章 字符串

• 07-01 字符串哈希详述
• 07-02 后缀数组

第八章 进阶

• 08-01 卷积与FFT
• 08-02 期望与概率
• 08-03 Zeta / Möbius 变换
• 08-04 计算几何基础
• 08-05 采样与随机化