二分答案：把最优化问题变成判定问题

很多学生第一次遇到”求最小值”三个字就条件反射地想 DP、二分、贪心三选一，有时候三个人都试一遍，最后发现根本不是这三类问题。

真正让人抓狂的是另一类题：题目里每个字都认识，但”最优化”三个字让人无从下手，因为答案既不是最大值也不是最小值，它藏在某个实数区间里。这时候二分答案是最好用的工具。它的核心思想只有一句话：

不要直接去求那个最优解，改成”猜一个答案，然后判断这个答案行不行”。

一旦能判断，答案空间再大也没关系——因为你每次猜错都能砍掉一半。

思路

一、先问能不能判：单调性是唯一前提

二分答案的前提不是”答案是个数”，而是 check 函数具有单调性。

设候选答案是 $x$，check(x) 表示”当答案取 $x$ 时是否存在可行方案”。二分能跑，当且仅当 check 的结果在答案区间上不出现真假交替：

• 前假后真：$x$ 太小不行，$x$ 够大就行（找第一个真的位置）
• 前真后假：$x$ 大了不行，$x$ 够小就行（找最后一个真的位置）

看图里那个例子：候选值 1 到 8，check 在 1、2、3 处为假，在 4 到 8 处为真。分界点 4 就是答案。二分做的事，就是每轮砍掉一半候选，把区间 $[1,8] \to [1,4] \to [3,4] \to [4,4]$ 收缩到一个点。

判定失败的两种典型情况，一定要能当场识别出来：

反例一，check 不单调。比如”求一个数 x，使得 x 的各位数字之和等于 10”。数字和随 x 剧烈波动，x=19 时和为 10，x=20 时和为 2，x=28 时又是 10。这类 check 二分必然错，而且错得很隐蔽——程序不会崩，只会安静地给出错误答案。

反例二，”前真后假”和”前假后真”搞反。比如”最少切几刀”，你写的 check 是 check(k) = 能不能用 k 刀切完"，那是前真后假（刀多了总能切完），找最后一个真的 k。但如果你写成check(k) = 需要的最少刀数 ≤ k`，语义等价，也是前真后假，同一个命题的两种写法方向是相反的。所以最稳的做法是：先在纸上写清 check 的语义，再决定用哪个模板，而不是凭感觉套模板。

二、整数二分：两个够用的模板

整数二分的写法很多，但考试和实战中只需要两个模板，而且必须分清”闭区间写法”和”半开区间写法”，因为它们对 mid 的取整方向要求正好相反。

模板一：找第一个满足 check(mid) == true 的位置（check 前假后真时用）

// 闭区间 [l, r] 内，假定至少有解
long long l = 1, r = n, ans = -1;
while (l <= r) {
    long long mid = l + (r - l) / 2;   // 向下取整
    if (check(mid)) {
        ans = mid;      // mid 可能是答案，但左边还有更小的
        r = mid - 1;     // 继续往左找
    } else {
        l = mid + 1;     // mid 不行，右边才有可能
    }
}

模板二：找最后一个满足 check(mid) == true 的位置（check 前真后假时用）

// 半开区间 [l, r)，r 为不可达哨兵
long long l = 0, r = n + 1;
while (l < r) {
    long long mid = l + (r - l + 1) / 2;   // 向上取整，注意 +1
    if (check(mid)) {
        l = mid;            // 可行端往右推
    } else {
        r = mid - 1;
    }
}
// 答案为 l - 1（最后一个为真的位置）

二·补：取整方向由「真分支往哪边走」决定，别死记

取整方向和哪一条分支在收缩是配套的，判断标准是：为真时更新的那个端点，能否保证严格变化。

// 形态 A：真分支让 l 右移 / r 左移（"往外扩"）→ 向上取整
while (l < r) { mid = l + (r - l + 1) / 2;
                if (check(mid)) l = mid; else r = mid - 1; }

// 形态 B：真分支让 r 左移 / l 右移（"往里收"，即 lower_bound 式）→ 向下取整
while (l < r) { mid = l + (r - l) / 2;
                if (check(mid)) r = mid; else l = mid + 1; }

形态 B 向下取整为什么也安全？因为 while (l < r) 保证 $r - l \ge 1$，而 (r-l)/2 向下取整后必有 $mid \le r - 1 < r$，所以 a[mid] 不会越界，r = mid 也至少把区间缩到 $r$ 自身。但若写成向上取整，mid 可能等于 r，越界访问。 下面的例题一恰好用到了形态 B，这也是为什么它不需要 +1。

三、死循环到底是怎么产生的

学生写的二分死循环，十有八九来自 mid 的取整方向和区间开闭不匹配。这里把机理讲透，比背结论有用得多。

关键不变式：每一轮循环，区间长度必须严格变小。

模板一用 while (l <= r)，此时区间至少有一个元素，mid = l + (r-l)/2 向下取整后必然满足 $l \le mid \le r$：

• 若 check 为假，走 l = mid + 1，因为 $mid \ge l$，新长度 $r-l+1$ 至少减少 1；
• 若 check 为真，走 r = mid - 1，因为 $mid \le r$，新长度同样至少减少 1。

最极端的情况是 l == r：mid == l，两条分支分别得到 l = l + 1 > r 或 r = r - 1 < l，循环立即结束。闭区间 + 向下取整，是安全的。

模板二用 while (l < r)，区间至少有两个元素。此时如果还用向下取整的 mid = l + (r-l)/2，当 $r = l+1$ 时会算出 mid == l。若此时 check(mid) 为真，执行的却是 l = mid，区间完全没变——死循环就此诞生。所以这种形态必须用 +1 改成向上取整，保证 $mid \ge l+1$，l = mid 这一步才能真正推进。反过来，r = mid - 1 在 $mid \ge l+1$ 时也保证 $mid - 1 \ge l < r$，同样严格收缩。

一句话记住取整规则：真分支让 l 右移就用向上取整，真分支让 l 停住或让 r 左移就用向下取整。 上面 2·补节给了两种成对形态，实际写代码时对照着抄即可。

顺带说一句很多人忽略的点：用 (l + r) / 2 而不是 l + (r - l) / 2，在值域达到 $10^{18}$ 时会溢出。因为 l + r 最大接近 $2 \times 10^{18}$，超过了 long long 的 $9.22 \times 10^{18}$ 的一半，看起来安全，但一旦初值给成 $r = 4 \times 10^{18}$ 就会溢出成负数，程序会静默崩溃或死循环。养成写 l + (r - l) / 2 的习惯，零成本。

四、浮点二分：eps 不是随便填的

整数答案用整数二分，浮点答案（”保留两位小数””误差不超过 $10^{-6}$“）用浮点二分。写法上有个明显差别：浮点二分没有 ans 变量，直接把区间收缩到比 eps 还窄，然后按题目要求取整输出。

double l = 0.0, r = 1e9, eps = 1e-6;
while (r - l > eps) {
    double mid = (l + r) / 2.0;
    if (check(mid)) r = mid;    // 前假后真：右边才是解
    else            l = mid;
}
// 答案落在 [l, r] 内，长度已小于 eps

这里有三个坑，逐个说清楚：

第一，浮点二分的终止条件是 r - l > eps，不是 l <= r。 因为 l 和 r 是浮点数，它们之间的差距会趋近于 0 但永远不必然等于 0，闭区间写法在这里没有意义。

第二，eps 必须大于值域上的一个最小可表示间隔（ulp），否则同样会死循环。 这是浮点二分最隐蔽的坑。double 只有 53 位尾数，相对精度约 $2^{-53} \approx 1.1 \times 10^{-16}$。当值在 $10^9$ 附近时，相邻可表示浮点数的间隔约为 $1.2 \times 10^{-7}$。此时如果写 eps = 1e-9，条件 r - l > 1e-9 永远成立（因为 r 和 l 已经是相邻的浮点数了，再怎么取中点还是它们自己），循环停不下来。经验规则：eps 取题目允许误差的十分之一到百分之一，同时不要比值域 ulp 小。 另外值域很大（$10^{15}$ 以上）时，用 long double 能显著降低 ulp，把 ulp 降到 $10^{-4}$ 量级。

第三，浮点二分的答案取 l 还是 r，要看语义。 循环结束时 $[l, r]$ 的关系只有三种：答案是 $l$、答案是 $r$、或答案落在两者之间。所以稳妥做法是像上面这样保留 r 作为”可行的一端”，因为每轮 r = mid 只在 check(mid) 为真时执行，r 始终是一个可行值。当题目要求”保留两位小数”时，用 printf("%.2f", r) 之前，最好在 1e-6 精度上验证一下四舍五入的边界情况；更保险的写法是先二分到 1e-9，再用 llround 之类的手段按题目规则取整。

五、二分答案 + 贪心判定：通用套路

这是二分答案最常见的形态，套路可以概括成一句话：

答案空间大得没法枚举，但”给定答案，能不能做到”可以贪心地 O(n) 判完。

典型题面是：”把 $n$ 个数分成 $k$ 个连续段，每段和不超过 $W$，求最小的 $W$。”（下一节有完整代码）

• 答案空间：$W \in [\max a_i,\ \sum a_i]$，可能到 $10^{14}$，枚举必超时；
• 判定：给定 $W$，从左到右贪心地装，能装就装，装不下就开新段，最后看段数是否 $\le k$；
• 单调性：$W$ 越大越宽松，段数只会减少，所以 check 前假后真，找第一个可行的 $W$。

同一套路换个马甲就是同一题：

题面	答案 $x$ 的含义	check 怎么做
最少切几刀把木头切完	每段最大长度	累加超了就新开段，数段数
最少多少个组能让每组重量和 $\le W$	组数	同上
最小速度 T 秒内能跑完全程	速度 $v$	按距离累加时间，超了就换人
最长公共上升子序列至少多长	答案长度 $k$	DP 判定（不是贪心）

注意最后一行：当 check 本身需要 DP 时，二分答案依然成立，DP 套二分是常见组合，只是 check 变成了 $O(n^2)$ 或 $O(nk)$，总复杂度是 $O(\log V \cdot \text{check})$。判断依据始终是单调性，而不是”check 必须贪心”。

六、和三分、分治、倍增的边界

这四个东西长得很像，都是”每次缩小一半”，但适用条件完全不同。

手段	二分的对象	成立条件	典型签名
二分答案	check 的真假	check 单调（前假后真 / 前真后假）	“能否可行”、”是否满足”
三分	函数值的大小	$f(x)$ 单峰（先增后减）或单谷	代价函数不是阶梯状的极值
分治	问题规模	拆成同类子问题且能合并答案	归并排序、快速排序、CDQ 分治
倍增	一次跳多远	前缀单调 + 跳跃步长为 2 的幂	LCA、第 $k$ 级祖先、求最早达标位置

几个容易混的点：

二分和三分的区别是”真假”与”大小”。 二分只问 check 是不是真，check 内部可以毫无梯度（阶梯状、跳变）；三分必须比较 $f(mid)$ 和 $f(mid+\varepsilon)$ 的大小，所以要求 $f$ 本身单峰。如果代价函数是阶梯状的（跳一下变很多），三分一定会错，二分却是对的。 比如”分割数组使最大段和最小”，代价随 $W$ 变化是阶梯的，只能二分。

二分和分治的区别是”求解”与”排除”。 二分每轮只把答案定位到一半区间，其他半边直接丢弃，不承担计算责任；分治是把问题拆成两个都要算的子问题，再合并。二者可以嵌套（归并排序统计逆序对时，先分治划分区间，再对跨区间部分二分）。

倍增是二分的一个特化写法。 它的独特之处在于：维护一个窗口 $[i, j)$，每次尝试 $j = i + 2^k$，成功就把 $k$ 减半继续跳，失败就换更大的 $k$ 试试，本质是在用二进制拼出一个尽量大的合法步数。它要求”从 $i$ 出发可达 $[i, j)$ 内任一点，且可达性关于 $j$ 单调”。判断标准很简单：如果你的需求是”最远的可行位置”且步长是 2 的幂，用倍增；如果需求是”最小可行的 $x$“且判定是布尔判定，用二分。 倍增还大量用于预处理（ST 表求区间最值、倍增 LCA），这类用途跟二分答案毫无关系，别混为一谈。

正确性

以本文代码里的第二道题（分 $k$ 段、段和不超过 $W$）为例，证明三件事。

引理 1：贪心判定得到的段数是最少的。
贪心在每一段里尽可能多地装入元素，直到装不下下一个为止。假设存在另一种方案段数更少，把两种方案的第一段结尾位置对比：贪心的第一段结尾不会更靠前（否则说明贪心提前停了，与”装不下”矛盾）。逐段归纳，贪心在任意第 $t$ 段的结尾位置都不会落后于其他方案。因此当总元素个数固定时，贪心段数最少。∎

引理 2：check 具有前假后假单调性（check 前假后真）。
设 $W_1 < W_2$。任意一个在 $W_1$ 下可行的方案，把段上限放宽到 $W_2$ 后依然可行。所以 $\text{check}(W_1) = \text{true} \Rightarrow \text{check}(W_2) = \text{true}$。∎

定理：二分输出的 $W$ 是最小的可行段和上限。
由引理 2，check 在 $[\max a_i, \sum a_i]$ 上前假后真，满足模板一的前提。由引理 1，check 的判定本身正确。模板一保证二分返回第一个使 check 为真的位置，即最小的可行 $W$。∎

整数查找那道题的正确性同理：a 非降，所以 a[i] >= x 在下标序列上必然是”若干个假 + 若干个真”的形状，模板一返回第一个真（即第一个 $\ge x$ 的位置），模板二返回最后一个真（即第一个 $> x$ 的位置减一），两者相减即为 $x$ 的出现次数。

复杂度

• 整数二分：二分本体 $O(\log V)$ 次判定，$V$ 为答案区间大小。若 check 为 $O(n)$，总复杂度 $O(n \log V)$，空间 $O(1)$。
• 查找边界：$O(\log n)$ 次比较，时间 $O(\log n)$，空间 $O(1)$。
• 浮点二分：迭代次数为 $\log_2 \dfrac{r-l}{\varepsilon}$。以 $[0, 10^9]$、$\varepsilon = 10^{-6}$ 计算，约 50 次。

参考代码（C++17）

例题一：整数二分 —— 统计某个数在有序数组中出现的次数

要求用二分而非 std::count，并顺带演示两个模板如何配合。数组已按非降序给出，$x$ 可能不存在。

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    long long x;
    cin >> n >> x;

    vector<long long> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }

    // 前提：a 非降序。这一点由题目保证，不能省。

    // ---------- 模板一：找第一个 a[i] >= x 的位置 ----------
    // check(i) = (a[i] >= x) 在非降序数组上必然「前假后真」。
    // 用 l/r 都从 0 开始、n 作为"永远不可行"的哨兵。
    int lower = n;                      // 若全都不满足，则为 n
    {
        int l = 0, r = n - 1;           // 闭区间 [l, r]，n-1 是最后一个真实下标
        while (l <= r) {
            int mid = l + (r - l) / 2;  // 向下取整；写 l+(r-l)/2 而不是 (l+r)/2 防溢出
            if (a[mid] >= x) {
                lower = mid;           // mid 可行，记录并继续向左找更小的
                r = mid - 1;
            } else {
                l = mid + 1;            // mid 太小，右边才可能
            }
        }
    }

    // ---------- 模板二：找第一个 a[i] > x 的位置 ----------
    // a[i] > x 在非降序数组上是「前假后真」，仍可用 lower_bound 式二分。
    // 注意这里分支是 r=mid / l=mid+1（r 往下走），配向下取整即可；
    // 向上取整反而会算出 mid == r，越界访问。
    int upper = n;                      // 找第一个 > x 的位置
    {
        int l = 0, r = n;               // 半开区间 [l, r)，r = n 是不可达哨兵
        while (l < r) {
            int mid = l + (r - l) / 2;  // r-l>=1 且向下取整，保证 mid < r，不会越界
            if (a[mid] > x) {
                r = mid;                // mid 可行，答案在左半（含 mid）
            } else {
                l = mid + 1;            // mid 不行，答案在右侧
            }
        }
        upper = l;                      // 全部 <= x 时 l 会收敛到 n
    }

    // a[i] <= x 的最后一个位置就是 upper - 1。
    // 出现次数 = [lower, upper) 的长度，即 upper - lower。
    int cnt = upper - lower;
    cout << cnt << '\n';
    return 0;
}

例题二：二分答案 + 贪心判定 —— 最小的最大段和

给定 $n$ 个非负整数 $a_1 \dots a_n$ 和整数 $k$（$1 \le k \le n$）。把它们按原顺序划分成不超过 $k$ 个非空连续段，要求每段的元素和都不超过 $W$。求满足条件的最小的 $W$。

输入第一行 n k，第二行 $n$ 个非负整数。数据保证答案存在（$W = \sum a_i$ 一定可行）。$n \le 10^5$，$a_i \le 10^9$。

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, k;
    cin >> n >> k;

    vector<long long> a(n);
    long long sum = 0, mx = 0;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        sum += a[i];            // 所有元素之和：W 的一个合法上界
        mx = max(mx, a[i]);     // 最大元素：W 的一个合法下界
    }

    // 判定：段和上限为 W 时，最少需要多少段。
    // 贪心从左往右装，装不下就开新段。贪心得到的段数是最少的（引理 1）。
    // cnt 累到 k 就可以提前返回，因为我们只关心「是否超过 k」。
    auto check = [&](long long W) -> bool {
        int cnt = 1;            // 非空段，至少有 1 段
        long long cur = 0;      // 当前段的元素和
        for (int i = 0; i < n; ++i) {
            if (cur + a[i] <= W) {
                cur += a[i];    // 装得下就装，贪心地让这一段尽可能长
            } else {
                cnt++;          // 装不下，开新段
                if (cnt > k) {
                    return false;   // 已经超过 k 段，提前失败
                }
                cur = a[i];     // 新段从当前元素开始
            }
        }
        return cnt <= k;
    };

    // W 越大越宽松 ⇒ check 前假后真 ⇒ 用模板一找第一个可行位置。
    // 值域 [mx, sum]，sum 最大可达 1e14，必须用 long long。
    long long l = mx, r = sum, ans = sum;
    while (l <= r) {
        long long mid = l + (r - l) / 2;   // 防溢出写法
        if (check(mid)) {
            ans = mid;      // mid 可行，记录并继续向左找更小的
            r = mid - 1;
        } else {
            l = mid + 1;     // mid 不行，答案只能在右边
        }
    }

    cout << ans << '\n';
    return 0;
}

用样例 {2, 2, 2, 3, 1, 2, 5}，$k=3$ 手工推演一遍：

• $W = 6$：第一段 $[2,2,2]$ 和为 6；下一段 $[3,1,2]$ 和为 6；最后 $[5]$ 为 5。共 3 段，可行。
• $W = 5$：贪心装出 [2,2](4)、[2,3](5)、[1,2](3)、[5]，共 4 段 > 3，不可行。

所以答案是 6。二分的价值在于：如果枚举 $W$，要试约 $10^{14}$ 次；而二分只做 $\log_2(10^{14}) \approx 47$ 次判定，每次判定 $O(n)$，总复杂度 $O(n \log \sum a)$，轻松通过 $10^5$ 的数据。

易错点清单

1. 没验证单调性就开二分。 这是最贵的错误，因为它不报错。写完 check 后，一定要在小数据上把区间端点、中间点和若干随机点的 check 值打出来看看，确认没有真假交替。
2. mid 的取整方向和区间开闭不匹配导致死循环。 记住：while (l <= r) 配向下取整，while (l < r) 配向上取整（(r - l + 1) / 2）。
3. 用 (l + r) / 2 导致溢出。 值域上到 $10^{18}$ 时一律写 l + (r - l) / 2。
4. r 的初值没留好哨兵。 闭区间写法里 r 是真实可达的右端点；半开写法里 r 是”不可达”的哨兵。混用会得到 ans = -1 之类的静默错误。
5. 浮点二分的 eps 小于 ulp。 值域 $10^9$ 时 eps 不要低于 $10^{-6}$；值域更大时改用 long double。用 (l+r)/2 也可能因为精度损失而 mid 无法严格落在区间内，此时 l = mid 不推进，同样死循环——规避办法就是别把 eps 设得过小。
6. 浮点二分输出了 l 而不是 r。 r 始终是可行的一端，l 始终是不可行的一端，要”可行解”就输出 r。
7. 答案空间开窄了或开宽了。 下界用 $\max a_i$（单个元素独占一段都放不下的话无解）、上界用 $\sum a_i$（单段一定可行）。下界开得比真答案小不会错，只是多几次判定；开得比真答案大就直接 WA。
8. 贪心判定写成了”能放就放、否则失败”。 背包类判定里放不下时应该是”开新段”，而不是立刻返回失败；只有段数超限才失败。
9. 段数初值设成 0。 非空划分至少有一段，cnt 应从 1 开始，否则 $k = n$ 之类边界会算错。
10. 把二分和三分搞混。 代价函数是阶梯跳变的，三分必错，二分才对；反之若函数光滑单峰，用二分去找”是否存在解”往往无从下手。