二分搜索

前言：一个猜数字游戏的启示

我想了一个 1 到 100 之间的整数，你来猜。每次猜完我告诉你”大了”还是”小了”。你当然不会从 1 开始挨个猜——你会先猜 50。如果我说”小了”，范围就缩到 51-100，再猜 75……每猜一次，候选范围就减半。最多猜 7 次（$\log_2 100 \approx 7$）就能找到答案。

这就是二分搜索——也许是计算机科学中最优雅的想法之一。

但它的用途远不止”在有序数组里找一个数”。很多看似和搜索无关的问题，本质上都在一个单调的空间里寻找答案。比如：

• “每段木材至少多长，才能切出 $k$ 段？“——长度越大越难切出 $k$ 段（单调性），二分这个长度
• “把数组分成 $m$ 段，每段和的最大值最小是多少？“——这个最大值有单调性，可以二分
• “第 $k$ 小的数对距离是多少？“——距离有单调性，可以二分

这篇笔记会先讲二分搜索的基础（在有序数组中查找），然后引出一个更通用的模式（找第一个满足条件的位置），最后展示”二分答案”的思路——这是竞赛中最高频的技巧之一。

二分搜索

问题的本质

在一个有序序列中查找目标值，朴素扫描 $O(n)$，但有序性提供了额外信息——可以每次排除一半。

关键洞察：只要能确定”答案在左半还是右半”，就能把搜索空间减半。$n \to n/2 \to n/4 \to \dots$，$O(\log n)$ 次即可收敛。

基础：在有序数组中找目标值

int binary_search(vector<int>& a, int target) {
    int lo = 0, hi = a.size() - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;  // 防溢出
        if (a[mid] == target) return mid;
        if (a[mid] < target) lo = mid + 1;
        else                 hi = mid - 1;
    }
    return -1;  // 未找到
}

要点：mid = lo + (hi - lo) / 2 而非 (lo + hi) / 2，后者在 lo + hi 超过 INT_MAX 时溢出。

更通用的模式：求满足条件的最小值

很多问题不是”找等于”，而是找第一个满足某条件的位置。

int lower_bound(vector<int>& a, int target) {
    int lo = 0, hi = a.size();  // 注意 hi 是 n，不是 n-1
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (a[mid] >= target) hi = mid;   // mid 满足条件，答案在 [lo, mid]
        else                  lo = mid + 1; // mid 不满足，答案在 (mid, hi)
    }
    return lo;  // lo == hi，第一个 >= target 的位置
}

为什么这个写法不会死循环？

• lo < hi 保证区间至少有 2 个元素
• hi = mid 缩上界，lo = mid + 1 缩下界，每次区间严格缩小
• 退出时 lo == hi，就是答案

二分的适用条件

不是只有”有序数组”才能二分。核心前提是单调性：

如果 $f(x)$ 是某个判定条件，且存在分界点 $p$ 使得 $x < p$ 时 $f(x)$ 为假、$x \ge p$ 时 $f(x)$ 为真，就可以对 $x$ 二分找 $p$。

这就是”二分答案”的思想——把优化问题转化为判定问题。

例题：木材加工

有 $n$ 根木材，长度分别为 $a_i$。要切出 $k$ 段等长的木材（不能拼接），求最大能切多长。若无法切出 $k$ 段则返回 0。

$1 \le n \le 10^5$，$1 \le k \le 10^8$，$1 \le a_i \le 10^8$

思路：直接枚举长度 $L$，对每个 $L$ 检查能切几段——每根木材贡献 $\lfloor a_i / L \rfloor$ 段。但 $L$ 的范围太大。

注意到：$L$ 越大，能切出的段数越少（单调性）。所以对 $L$ 二分，判定条件是”段数是否 $\ge k$”。

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

int main() {
    int n, k;
    scanf("%d%d", &n, &k);
    vector<int> a(n);
    for (int i = 0; i < n; i++) scanf("%d", &a[i]);

    long long lo = 1, hi = *max_element(a.begin(), a.end());
    long long ans = 0;
    while (lo <= hi) {
        long long mid = lo + (hi - lo) / 2;
        long long cnt = 0;
        for (int x : a) cnt += x / mid;
        if (cnt >= k) { ans = mid; lo = mid + 1; }  // 满足，尝试更大的
        else           { hi = mid - 1; }
    }
    printf("%lld\n", ans);
    return 0;
}

解析：二分范围 $[1, \max a_i]$，每次 check 扫一遍数组 $O(n)$，总共 $O(n \log(\max a_i))$。这是”二分答案”的经典范式——不直接求答案，而是在答案空间上二分，每步做一次判定。