C++二分答案法：不只是查找，更是解题思路

提起C++二分查找，大多数人的第一反应是在一个有序数组中快速找到某个值。但二分的思想远不止于此——二分答案法将“猜答案”与“验证可行性”结合，把优化问题转化为判定问题，在算法竞赛中频频上演“化不可能为可能”的好戏。

无数次，当你面对“最大值最小化”或“最小值最大化”的题目束手无策时，二分答案往往能为你打开一扇新的大门。本文将从原理、适用条件、典型模型到 C++ 实现细节，系统讲解二分答案法，助你彻底掌握这一思想。

一、从“在数组中找数”到“在答案空间中找解”

普通二分查找的前提是单调序列：给定一个已排序的数组，我们可以通过不断折半缩小查找范围。二分答案法继承了这一核心——答案空间必须具有单调性。

什么叫答案空间的单调性？假设我们要求解某个最优化问题的答案 x，并且存在一个判定函数 check(mid)，能够回答“当答案为 mid 时，是否可行？”如果对于所有小于等于某个阈值 t 的 mid，check(mid) 都返回 true，而大于 t 的都返回 false（或者反过来），那么我们就拥有了一个单调的分界点。这个分界点就是最优解。

典型场景：

• 最大值最小化：将问题转化为“能否使最大值不超过 mid”，随着 mid 增大，可行性从假变真（单调递增）。

• 最小值最大化：将问题转化为“能否使最小值至少为 mid”，随着 mid 增大，可行性从真变假（单调递减）。

二分答案的过程就是：在答案的可能范围 [l, r] 中，不断取中点 mid，调用 check(mid)，根据返回值调整左右边界，最终收敛到最优解。

二、二分答案的适用条件（必看！）

不是所有题目都能用二分答案。使用前请确认三个条件：

1. 答案具有单调性：当答案变量增大时，可行性状态只变化一次（从可行到不可行，或反之）。

2. 易于判定可行性：check(mid) 的实现复杂度低（通常是 O(n) 或 O(n log n)），否则二分带来的 log 收益会被拖累。

3. 答案空间范围可接受：二分需要 O(log (R-L)) 次判定，R-L 通常在 1e9 内，即约 30-60 次判定，可以接受。

如果满足以上条件，二分答案往往比直接求解更简单、更高效。

三、经典例题一：木材切割（最大值最小化）

问题描述：有 n 根木材，长度分别为 L[i]。需要将它们切割成 k 段长度相同的小段（每段长度可以为非整数？竞赛中通常为整数）。求每段最大可能的长度（即切成 k 段后允许的最大长度）。

分析：如果直接求最大长度较困难，但我们可以判断一个长度 mid 是否可行：计算每根木材能切出多少段长度为 mid 的小段，看总数是否 ≥ k。显然，mid 越小，可切出的段数越多，可行性单调递增。因此二分答案。

C++ 实现：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 5;
int n, k;
int L[N];

bool check(int x) {
    ll cnt = 0;
    for (int i = 0; i < n; ++i) {
        cnt += L[i] / x;
        if (cnt >= k) return true;  // 提前退出
    }
    return cnt >= k;
}

int main() {
    cin >> n >> k;
    int max_len = 0;
    for (int i = 0; i < n; ++i) {
        cin >> L[i];
        max_len = max(max_len, L[i]);
    }
    int l = 1, r = max_len, ans = 0;
    while (l <= r) {
        int mid = l + (r - l) / 2;
        if (check(mid)) {
            ans = mid;
            l = mid + 1;   // 尝试更大的长度
        } else {
            r = mid - 1;
        }
    }
    cout << ans << endl;
    return 0;
}

关键点：二分边界采用闭区间 [l, r]，当 check(mid) 为真时，记录答案并往右半区找更大值；否则往左半区找。

四、经典例题二：奶牛挤奶（最小值最大化）

问题描述：在一条直线上有 n 个点（位置 x[i]），选择其中 k 个点作为奶牛的牛舍，使得任意两个牛舍之间的最小距离尽可能大。求这个最大化的最小距离。

分析：直接安排位置很难。但我们可以判定：最小距离为 mid 是否可行？贪心策略：将点排序后，从第一个点开始，依次选取距离上一个选中的点 ≥ mid 的点，直到选满 k 个或遍历结束。若最后能选到 ≥ k 个，则 mid 可行。显然，mid 越大越难满足，可行性单调递减。因此二分答案。

C++ 实现：

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int n, k;
int pos[N];

bool check(int mid) {
    int cnt = 1;
    int last = pos[0];
    for (int i = 1; i < n; ++i) {
        if (pos[i] - last >= mid) {
            cnt++;
            last = pos[i];
            if (cnt >= k) return true;
        }
    }
    return cnt >= k;
}

int main() {
    cin >> n >> k;
    for (int i = 0; i < n; ++i) cin >> pos[i];
    sort(pos, pos + n);
    int l = 1, r = pos[n-1] - pos[0], ans = 0;
    while (l <= r) {
        int mid = l + (r - l) / 2;
        if (check(mid)) {
            ans = mid;
            l = mid + 1;   // 尝试更大距离
        } else {
            r = mid - 1;
        }
    }
    cout << ans << endl;
    return 0;
}

五、进阶技巧：实数二分与精度控制

有些问题的答案不是整数，例如求浮点数的平方根，或者“在某个精度下求最大长度”。此时需要使用实数二分。

模板（以浮点数为例）：

double l = 0, r = 1e9;
for (int i = 0; i < 80; ++i) {   // 固定迭代次数，保证精度
    double mid = (l + r) / 2;
    if (check(mid)) l = mid;     // 可行，向右侧逼近
    else r = mid;
}
printf("%.10f\n", l);

通常 80 次循环足以将精度提到 2^{-80} 量级，远高于题目要求（1e-9）。不建议用 while (r - l > eps)，因为 eps 取值不当可能死循环或精度不足，固定次数更安全。

六、复杂判定函数的优化技巧

check(mid) 是二分答案法的核心，其效率直接影响整体复杂度。好的判定函数应该：

• 尽可能 O(n) 或 O(n log n)。

• 提前剪枝（如累计计数超过目标就返回）。

• 利用贪心、前缀和、滑动窗口等技巧。

例：最大值最小化中的“装车问题”：将 n 个物品按顺序装车，每辆车容量为 mid，求最少需要多少辆车，并与给定车数比较。判定函数只需一趟扫描 O(n)。

例：最小值最大化中的“放置问题”：贪心放置是 O(n)；有时还需要动态规划或贪心 + 二分（如“牛舍”问题）。

七、二分答案的边界处理（避坑指南）

边界是初学者出错最多的地方。常见错误及解决方案：

1. 死循环：当 l = mid 且 mid = (l+r)/2 向下取整时，若 l = r-1 且 check(l) 为真，mid = l， l = mid 导致区间不变。解决办法：使用 mid = (l+r+1)/2 向上取整，或者采用 l = mid+1 和 r = mid-1 的闭区间写法。

2. 答案不在范围内：初始的 l 和 r 必须保证答案在区间内。例如木材切割最小长度至少为 1，最大为 max(L)。如果可能无解，需单独判断。

3. 整数溢出：mid = l + (r - l) / 2 优于 (l+r)/2 防止大整数加和溢出。

推荐通用模板：

int l = min_possible, r = max_possible;
int ans = -1;
while (l <= r) {
    int mid = l + (r - l) / 2;
    if (check(mid)) {
        ans = mid;
        l = mid + 1;   // 向右搜
    } else {
        r = mid - 1;
    }
}
// ans 即最优解（若存在）

对于“最小值最大化”同样适用，只需调整 check 的含义和 ans 的更新方向。

八、与动态规划、贪心的结合

二分答案法往往不是孤立的，而是与其它算法配合。例如：

• 二分 + 前缀和：判断区间和是否满足某个条件。

• 二分 + 贪心：如上文牛舍问题。

• 二分 + 最短路：在“边权最大值的最小化”问题中，二分最大边权，然后用 BFS/DFS 或并查集检查连通性。

• 二分 + 网络流：二分答案后建图，判断最大流是否达到需求。

九、实战案例：借教室（洛谷 P1083）

题意：有 n 天，每天可租借的教室数量为 r[i]。有 m 个订单，每个订单要求从第 s 天到第 t 天每天租用 d 个教室。问第一个无法满足的订单是第几个，或者全部满足。

解法：直接模拟逐天扣减会超时。但我们可以二分答案 mid（表示前 mid 个订单能否同时满足）。check(mid) 方法：使用差分数组将前 mid 个订单的租用需求叠加到每一天，然后判断是否超过 r[i]。复杂度 O(n + m)，二分 O(log m)，总 O((n+m) log m)。

这展示了二分答案法在“判定一个前缀是否可行”上的强大威力。

十、总结：二分答案法的思维模型

┌─────────────────────────────────────┐
│   最优化问题（最大值/最小值）         │
└─────────────┬───────────────────────┘
              ▼
┌─────────────────────────────────────┐
│   假设一个答案mid                     │
│   定义判定函数 check(mid)             │
│   是否满足约束条件？                   │
└─────────────┬───────────────────────┘
              ▼
┌─────────────────────────────────────┐
│   单调性检验                         │
│   如果 check(mid) 随 mid 单调变化     │
└─────────────┬───────────────────────┘
              ▼
┌─────────────────────────────────────┐
│   二分查找分界点                      │
│   得到最优解                         │
└─────────────────────────────────────┘

掌握二分答案法，意味着你拥有了一种将“求值”问题转化为“判定”问题的通用工具。它不能解决所有最优化问题，但能解决一大类具有单调性的问题。在未来的竞赛中，当你面对“最大值最小化”“最小值最大化”或类似的字眼时，请立刻想到二分答案。先用它构建一个朴素的 check 函数，如果 check 能在多项式时间内完成，你离 AC 已经不远了。

最后，记住：二分答案是一种思想，不是局限于数组查找的技巧。它教会我们，当直接求解困难时，不妨先猜一个答案，看看它是否可行——而这，正是计算机科学中“猜测与验证”范式的完美体现。