二分——学会即可碾压 90% 的程序员！

iChen · 2025-12-18 17:43:15 · 算法·理论

二分算法

二分是一种比较常用的算法，是分支思想的一种体现和应用，在后续算法竞赛学习的很多题目中都有对二分的体现和运用。

此文中我们会从二分的基础逐渐过渡到二分的复杂运用和其它算法的结合。

Part 1 二分查找

通过二分查找，我们可以初步理解二分的本质和思想。

1.1 引入

:::info[猜数游戏]{open} 小 A 在 1\sim100 中在心里随机挑选一个数字，小 B 会多次猜测这个数字具体的值，如果没猜中，小 A 会告诉小 B 他猜的属比答案大还是小。

请问小 B 运用什么策略能在最坏情况下用最小的次数猜中小 A 心中想的数字？ :::

一种最差的策略是逐个枚举，最坏情况需要猜 100 次。

我们需要充分利用小 A 提供的猜的数和答案的大小关系，不难想到我们可以每次猜一个中间的数，根据小 A 给出的信息向左右缩小答案区间，那么每次找哪一个中间的数是最好的？

理性证明： 我们目前确定了答案在 [l, r] 中，初始 l = 1, r = 100，每次会找到一个 mid\in[l, r] 来询问小 A，如果没猜中，根据小 A 给出的答案可以把答案确定在 [l, mid - 1] 和 [mid + 1, r] 中。在最坏情况下，我们得到的下一个区间应该是这两个区间中长度更大的一个，那么下一个区间长度就是 L = \max\{mid - l, r - mid\}，发现 mid = \dfrac{l + r}{2} 时能使 L 取最小值为 \dfrac{r - l}{2}，故我们每次只需要找到 l 和 r 的平均数，猜测并缩小答案区间，就能在最坏情况下使用最小次数猜出答案。

感性理解： 目前确定答案在一个范围内，找到中间的那个数询问，每次就一定能将这个区间缩小一半。但如果我们不选择中间的数，比如在第一次猜测时猜测 30，如果运气好可以直接猜出或把区间缩小到 [1, 29]，但在最坏情况下会将区间缩小到 [31, 100]，这样猜数使用的次数是不稳定的。每次选中间数一定能将区间缩小一半，是最稳定的策略。

这就是二分思想，每次对目前区间的中间数进行询问，固定将区间缩小一半，猜测的次数稳定在 \log \text{(区间初始长度)}。

尝试用代码实现：

int l = 1, r = 100;
int x; // 小 A 想的数 
while (true) {
    int mid = (l + r) / 2;
    if (mid == x) { // 此次猜测为答案
        cout << mid;
        exit(0); // 结束程序
    }
    if (mid < x) l = mid + 1;
    else r = mid - 1;
}

如果你觉得上面的代码太菜了：

int x; // 小 A 想的数
cout << x;

开挂行为切勿模仿。

1.2 整数的二分查找

:::info[二分查找/靠左]{open}

给出 n 个单调不减的非负整数 a_1, \cdots, a_n，进行 m 次询问，每次询问一个非负整数 x 在 a 中第一次出现的位置（下标），若未出现过输出 -1。

:::

不难发现，对于 a\geqslant0 与 a^3，a^3 随 a 增大而增大。那我们设 f(x) = x^3，则 f(x)具有单调性。我们便可以二分查找答案 x 使得 f(x) = n。

注意题目中的要求精度为 10^{-6}，那么我们对二分时的要求精度再小 10^{-2} 是最稳妥的，也就是 10^{-8}。那我们直接按照刚才整数域上的二分方法来二分即可，停止条件为 r - l \leqslant 10^{-8}。

可以写出以下代码：

#include <iostream>
#include <iomanip>

using namespace std;

double n;
constexpr double eps = 1e-8;

int main () {
    cin >> n;
    double l = 1, r = 100;
    while (r - l > eps) {
        double mid = (l + r) / 2;
        if (mid * mid * mid < n) l = mid;
        else r = mid;
    }
    cout << fixed << setprecision(6) << l;
    return 0;
}

以上即为基本的二分查找，完成习题以巩固对二分思想的初步认识。

Part 2 二分答案

二分答案是二分的进阶运用，也是经常使用的算是一种 trick。我们将从简单的二分答案思想认识逐步进阶到二分答案与其它算法结合的各种题目。

2.1 基础例题

二分答案最好结合题目来理解。

:::info[木材加工]{open} 伐木场有 n 根原木，每根的长度分别为 a_i，现在想要锯成 k 段长度均为 l 的木材，请最大化 l。

显然可以二分 y 判断可行性。答案点 (x, y) 应当使 \forall i\in[1, n),y \geqslant k_ix + b_i。所以对于 k_i \not= 0 的直线，可以把对于确定的 y 的横坐标左右范围缩小到 \frac{y - b}{k} 左右，那么可以先将 k_i = 0 的直线中最大的 b 找出设为二分下界，再在每次判断 mid 可行性时讨论每一条直线，将 x 的可行区间逐步缩小，最后如果还存在可行的 x，则具有可行性。

时间复杂度 \mathcal O(\log(\frac{Y}{eps})n)。

#include <iostream>
#include <iomanip>
#include <algorithm>
#define double long double

using namespace std;
using PII = pair <double, double>;

constexpr int N = 5e3 + 5;
constexpr double eps = 1e-5;
int n;
PII node[N];

struct StraightLine {
    double k, b;
} sl[N];

inline void getf (int id, PII a, PII b) {
    sl[id].k = (a.second - b.second) / (a.first - b.first);
    sl[id].b = a.second - sl[id].k * a.first;
}

inline bool check (double y) {
    double liml = 0, limr = 1e5;
    for (int i = 1; i <= n; ++ i) {
        double gtx = (y - sl[i].b) / sl[i].k;
        if (sl[i].k == 0) continue;
        if (sl[i].k > 0) {
            limr = min(limr, gtx);
        } else {
            liml = max(liml, gtx);
        }
        if (liml > limr) return false;
    }
    return true;
}

int main () {
    cin >> n;
    for (int i = 1; i <= n; ++ i) {
        cin >> node[i].first >> node[i].second;
        if (i != 1) getf(i - 1, node[i - 1], node[i]);
    }
    n --;
    double l = 0, r = 1e6, ans = 1e6;
    for (int i = 1; i <= n; ++ i) {
        if (sl[i].k == 0) l = max(l, sl[i].b);
    }
    while (r - l > eps) {
        double mid = (l + r) / 2;
        if (check(mid)) r = mid - eps, ans = mid;
        else l = mid + eps;
    }
    cout << fixed << setprecision(6) << ans;
    return 0;
}

:::

:::info[天路]{open} 小 X 的梦中，他在西藏开了一家大型旅游公司，现在，他要为西藏的各个景点设计一组铁路线。但是，小 X 发现，来旅游的游客都很挑剔，他们乘火车在各个景点间游览，景点的趣味当然是不用说啦，关键是路上。试想，若是乘火车一圈转悠，却发现回到了游玩过的某个景点，花了一大堆钱却在路上看不到好的风景，那是有多么的恼火啊。

所以，小 X 为所有的路径定义了两个值，V_i 和 P_i，分别表示火车线路的风景趣味度和乘坐一次的价格。现在小 X 想知道，乘客从任意一个景点开始坐火车走过的一条回路上所有的 V 之和与 P 之和的比值的最大值。以便为顾客们推荐一条环绕旅游路线（路线不一定包含所有的景点，但是不可以存在重复的火车路线）。

于是，小 X 梦醒之后找到了你……

输入第一行两个正整数 N,M，表示有 N 个景点，M 条火车路线，火车路线是单向的。

以下 M 行，每行 4 个正整数，分别表示一条路线的起点，终点，V 值和 P 值。

注意，两个顶点间可能有多条轨道，但一次只能走其中的一条。