二分的代码很短，难点却从来不在那几行循环里。

有时我们在有序数组中寻找一个位置，有时在答案范围中寻找可行与不可行的分界点；还有一些题，原始信息看不出任何规律，需要先转换问题，才能得到可以二分的判定函数。

这一篇从边界二分开始，接着整理二分答案、实数二分以及几种不那么直接的二分。正文不依赖配图，重点放在单调性的来源、判定函数的设计和闭区间写法的边界。

二分到底在找什么

从查找一个数到查找分界点

在一个单调不减的数组中查找$x$，最直接的想法是比较$a_{mid}$与$x$：

  • $a_{mid}<x$时，答案只可能在右侧；
  • $a_{mid}>x$时，答案只可能在左侧；
  • $a_{mid}=x$时，说明找到了一个等于$x$的位置。

如果数组中没有重复元素，到这里已经足够。但当$x$出现多次时，“找到一个$x$”和“找到第一个$x$”并不是同一件事。

例如：

1
2
下标：1 2 3 4 5 6
数值：1 2 2 2 5 8

寻找第一个$2$，其实是在寻找第一个满足$a_i\ge 2$的位置。把每个位置是否满足条件写出来：

1
2
位置：1     2    3    4    5    6
条件：false true true true true true

二分真正寻找的是 false 与 true 之间的分界点。

同理，寻找最后一个$a_i\le x$的位置，会得到：

1
2
位置：1    2    3    4     5     6
条件：true true true true false false

所以二分不只是在“猜一个数”。更准确地说，它在一个有序的搜索范围中寻找边界。

两种闭区间模板

本文统一使用闭区间$[l,r]$。循环进行时，$l$到$r$之间仍然是没有排除的候选位置。

寻找第一个满足条件的位置：

1
2
3
4
5
6
7
8
9
int ans = -1;
while (l <= r) {
    int mid = l + r >> 1;
    if (check(mid)) {
        ans = mid;
        r = mid - 1;
    }
    else l = mid + 1;
}

当 check(mid) 成立时，$mid$可能就是答案，因此先记录下来；但更靠左的位置仍然可能成立，所以继续搜索$[l,mid-1]$。

寻找最后一个满足条件的位置：

1
2
3
4
5
6
7
8
9
int ans = -1;
while (l <= r) {
    int mid = l + r >> 1;
    if (check(mid)) {
        ans = mid;
        l = mid + 1;
    }
    else r = mid - 1;
}

这里的方向正好相反。条件成立以后，继续向右寻找更大的可行位置。

这种写法有两个特点：

  1. 每次都会删除$mid$，因此不会在相邻位置之间死循环；
  2. 使用 ans 显式保存答案，循环结束后不需要再判断$l$和$r$分别指向哪里。

如果不存在满足条件的位置，ans 会保留初始值$-1$。有些题保证答案存在，也可以把它初始化成一个已知可行的边界。

mid、边界与溢出

代码中的：

1
int mid = l + r >> 1;

等价于：

1
int mid = (l + r) >> 1;

因为加法的优先级高于移位运算。只要$l+r$不会超过类型范围，这种写法没有问题。

如果$l,r$可能接近整数类型的上界，可以改成：

1
i64 mid = l + (r - l >> 1);

二分中的溢出不只可能发生在 mid。判定函数中的乘法、累计和以及上界计算更容易溢出。看到$10^{18}$一类的数据范围时，应该从输入、答案到 check 内部全部重新检查一遍类型。

二分答案

把最优化问题改成判定问题

有些题很难直接求出最优答案，却很容易回答：

如果答案取$x$，能不能完成？

设这个问题的结果为 check(x)。只要判定结果随着$x$单调变化，就可以二分出可行与不可行的分界点。

最常见的两种模型如下：

模型 常见判定结果 要找的边界
最大化最小值 true … true false … false 最后一个 true
最小化最大值 false … false true … true 第一个 true

“最大化最小值”通常是把限制$x$不断提高。要求越高，越难满足，因此可行答案集中在左侧。

“最小化最大值”通常是给出一个允许上限$x$。上限越大，越容易满足，因此可行答案集中在右侧。

名字只能帮助我们识别模型，最终仍然要证明 check(x) 的单调方向。不能看到“最大值”或“最小值”就直接套模板。

check 函数从哪里来

设计 check 时，先暂时忘记“怎样求最优”，只考虑“给定$x$以后怎样验证”。

常见的判定方式有：

  • 直接计算：算出制造$x$件物品的费用，判断是否超过预算；
  • 累计贡献：把每一段能够提供的贡献相加，判断是否达到目标；
  • 贪心：固定最短距离后，尽量保留或删除某些位置；
  • 排序：固定最大值后，把限制转换成截止时间，再检查能否安排；
  • 贡献转换：把平均值至少为$x$改写成若干项贡献和不小于$0$。

一个好的 check 只回答可行或不可行，不负责在内部重新求一次最优解。

搜索范围与复杂度

二分以前必须确定答案范围$[l,r]$：

  • $l$应该不大于真实答案；
  • $r$应该不小于真实答案；
  • 如果题目允许无解，还要准备一个不会与合法答案混淆的初始值。

上界可以来自题目数据，也可以由一个显然可行的方案推出。例如$n$个任务每秒完成一个，那么最后一个任务最多等待$n-1$秒，据此就能估计最大代价。

如果答案没有明显上界，但能够保证 check(x) 最终成立，可以先倍增找到一个可行上界：

1
2
i64 r = 1;
while (!check(r)) r <<= 1;

若答案为$A$，倍增只需要$O(\log A)$次判定。实际使用时仍要结合数据范围限制$r$，避免左移溢出；如果题目可能无解，也不能无限倍增。

如果一次 check 的时间复杂度为$O(T)$，答案范围长度为$V$，总时间复杂度为：

$$
O(T\log V)
$$

$\log V$通常不大，但 check 可能包含排序、贪心甚至另一层数据结构。分析复杂度时不能只写“二分是$O(\log V)$”。

实数二分与更一般的二分

实数二分

整数之间存在相邻关系，实数之间没有。因此实数二分不能使用$l\le r$和$mid\pm1$。

一种写法是当区间长度不超过 eps 时结束。下面假设 check(mid) 成立时继续向右，寻找最大的可行值：

1
2
3
4
5
6
double eps = 1e-10;
while (r - l > eps) {
    double mid = (l + r) / 2;
    if (check(mid)) l = mid;
    else r = mid;
}

这种写法直观，循环次数约为：

$$
O\left(\log_2\frac{r-l}{\varepsilon}\right)
$$

eps 应该比题目允许的误差更小。例如答案允许$10^{-6}$误差，可以取$10^{-9}$或$10^{-10}$，不要刚好取$10^{-6}$。

另一种写法是固定循环次数：

1
2
3
4
5
for (int t = 1; t <= 100; t++) {
    double mid = (l + r) / 2;
    if (check(mid)) l = mid;
    else r = mid;
}

循环$100$次以后，区间长度会缩小到原来的$2^{-100}$，已经远小于常见误差要求。它不需要反复调整 eps，也不会因为浮点精度使 mid 与某个端点重合而陷入死循环，所以竞赛中通常更稳定。

两种写法都正确。前者便于理解精度，后者更省心；如果寻找最小可行值，只需要把更新方向反过来。实数二分仍然需要单调性，输出保留六位小数也不代表计算精度只需要$10^{-6}$。

二分的对象不一定是最终答案

假设有一个二元函数$f(a,b)$。整个函数未必方便直接二分，但固定$a$以后，如果$f(a,b)$关于$b$单调，就可以枚举$a$并二分$b$。

这里二分的是“在当前$a$下，第一个使$f(a,b)$达到限制的$b$”，最终答案还需要在所有$a$的候选结果中取最优。

所以判断能否二分时，不必只盯着最终答案。数组下标、时间、长度、某个变量，甚至一个不断扩大的集合，都可能成为搜索对象。

单调性也可以主动构造

有些题的原始返回值会上下波动，看起来无法二分。但我们真正需要的只是一个布尔判定：

$$
\mathrm{false},\ldots,\mathrm{false},\mathrm{true},\ldots,\mathrm{true}
$$

如果能够通过奇偶性、前缀、补集或者数学变换，把原始信息转换成这样的判定结果，仍然可以二分。

后面的 Codeforces 2219B2 就属于这种情况。查询答案本身不单调，但“当前前缀是否已经包含三个目标位置”是单调的。

例题与典型应用

下面七道题分别对应边界查找、整数二分、贪心判定、二元函数、排序判定、实数二分和构造单调性。

题目 二分对象 判定或比较方式
洛谷 P2249 查找 第一个合法下标 $a_{mid}\ge x$
Codeforces 1613C Poisoned Dagger 最小毒药持续时间 累计伤害是否达到$h$
洛谷 P2678 跳石头 最大的最短距离 贪心移除数量是否不超过$M$
AtCoder ABC246 D 2-variable Function 固定$a$后的最小$b$ $f(a,b)\ge N$
AtCoder ABC023 D 射击王 最小的最大高度 截止时间能否全部满足
AtCoder ABC034 D 食盐水 最大可行浓度 最大的$K$项贡献和是否非负
Codeforces 2219B2 Unique Values 三个目标位置 奇偶性是否不同

例题一：洛谷 P2249 查找

题目链接：洛谷 P2249 查找

给定一个单调不减的数组，每次询问数字$x$第一次出现的位置；如果不存在，输出$-1$。

把条件写成$a_i\ge x$，二分第一个满足条件的位置。找到边界以后，再判断该位置是否真的等于$x$。

为什么不直接把条件写成$a_i=x$？因为相等位置的左侧和右侧可能都存在不相等的位置，判定结果不是一个连续的 false/true 区间。而$a_i\ge x$在有序数组上一定具有单调性。

点击展开完整代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/* Fufffh */
#include <bits/stdc++.h>
using namespace std;
using i32 = int32_t; using i64 = int64_t; using i128 = __int128_t;
using u32 = uint32_t; using u64 = uint64_t; using u128 = __uint128_t;

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

    int n, m;
    cin >> n >> m;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= m; i++) {
        int x, l = 1, r = n, p = -1;
        cin >> x;
        while (l <= r) {
            int mid = l + r >> 1;
            if (a[mid] >= x) {
                p = mid;
                r = mid - 1;
            }
            else l = mid + 1;
        }
        if (p == -1 || a[p] != x) p = -1;
        cout << p << " \n"[i == m];
    }
    return 0;
}

每次询问的时间复杂度为$O(\log n)$，空间复杂度为$O(n)$。

例题二：Codeforces 1613C Poisoned Dagger

题目链接：Codeforces 1613C Poisoned Dagger

在$a_1,a_2,\ldots,a_n$时刻发动攻击。每次攻击施加持续$k$秒的毒素；如果上一轮毒素尚未结束，新攻击会直接刷新持续时间。求造成至少$h$点伤害所需的最小$k$。

相邻两次攻击之间的间隔为$a_{i+1}-a_i$。第$i$次攻击在下一次刷新以前最多造成：

$$
\min(k,a_{i+1}-a_i)
$$

最后一次攻击后面没有新的攻击，一定可以贡献$k$。因此总伤害为：

$$
damage(k)=k+\sum_{i=1}^{n-1}\min(k,a_{i+1}-a_i)
$$

$k$越大，每一项都不会减小，所以总伤害单调不减。我们要找第一个满足$damage(k)\ge h$的$k$。

答案不会超过$h$：即使只有最后一次攻击，持续$h$秒也能造成$h$点伤害。因此搜索范围可以直接取$[1,h]$。

点击展开完整代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
/* Fufffh */
#include <bits/stdc++.h>
using namespace std;
using i32 = int32_t; using i64 = int64_t; using i128 = __int128_t;
using u32 = uint32_t; using u64 = uint64_t; using u128 = __uint128_t;

void solve() {
    int n;
    i64 h;
    cin >> n >> h;
    vector<i64> a(n);
    for (i64 &x : a) cin >> x;

    i64 l = 1, r = h, ans = h;
    while (l <= r) {
        i64 mid = l + r >> 1;
        i64 sum = mid;
        for (int i = 0; i + 1 < n; i++) {
            sum += min(mid, a[i + 1] - a[i]);
            if (sum >= h) break;
        }
        if (sum >= h) {
            ans = mid;
            r = mid - 1;
        }
        else l = mid + 1;
    }
    cout << ans << '\n';
}

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

    int t;
    cin >> t;
    while (t--) solve();
    return 0;
}

单次判定为$O(n)$，总时间复杂度为$O(n\log h)$，空间复杂度为$O(n)$。

例题三：洛谷 P2678 跳石头

题目链接：洛谷 P2678 跳石头

河道长度为$L$，中间有$n$块岩石，最多移走$m$块。要求移除以后，相邻落脚点之间的最短距离尽可能大。

假设最短距离至少为$x$。从起点开始扫描，如果当前岩石与上一块保留岩石的距离小于$x$，当前岩石就不能保留；否则更新上一块保留岩石。

这种贪心始终尽量保留更靠左的岩石，为后面的跳跃留下更大的空间。扫描结束后，如果需要移除的岩石不超过$m$，说明$x$可行。

$x$越大，需要移除的岩石只会更多，因此判定结果为：

$$
\mathrm{true},\ldots,\mathrm{true},\mathrm{false},\ldots,\mathrm{false}
$$

我们要找最后一个可行的$x$。

点击展开完整代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
/* Fufffh */
#include <bits/stdc++.h>
using namespace std;
using i32 = int32_t; using i64 = int64_t; using i128 = __int128_t;
using u32 = uint32_t; using u64 = uint64_t; using u128 = __uint128_t;

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

    int len, n, m;
    cin >> len >> n >> m;
    vector<int> a(n + 2);
    for (int i = 1; i <= n; i++) cin >> a[i];
    a[n + 1] = len;

    auto check = [&](int x) {
        int cnt = 0, lst = 0;
        for (int i = 1; i <= n + 1; i++) {
            if (a[i] - a[lst] < x) cnt++;
            else lst = i;
        }
        return cnt <= m;
    };

    int l = 1, r = len, ans = 0;
    while (l <= r) {
        int mid = l + r >> 1;
        if (check(mid)) {
            ans = mid;
            l = mid + 1;
        }
        else r = mid - 1;
    }
    cout << ans << '\n';
    return 0;
}

单次判定为$O(n)$，总时间复杂度为$O(n\log L)$，空间复杂度为$O(n)$。

终点不能真的被移除。代码在终点距离不足时把计数增加一次，可以理解为移除上一块保留的岩石，让终点与更早的岩石直接相连；只需要判断最少移除数量是否超过$m$，计数结果仍然正确。

例题四：AtCoder ABC246 D 2-variable Function

题目链接：AtCoder ABC246 D 2-variable Function

给定$N$，求不小于$N$的最小整数$X$，并且存在非负整数$a,b$满足：

$$
X=a^3+a^2b+ab^2+b^3
$$

记：

$$
f(a,b)=a^3+a^2b+ab^2+b^3
$$

直接二分$X$并不好判断，因为“是否存在$a,b$使$f(a,b)=X$”并不单调。

换一个方向：枚举$a$。当$a$固定时，$f(a,b)$随着$b$单调递增，可以二分第一个满足$f(a,b)\ge N$的$b$，再用$f(a,b)$更新答案。

由于$f(10^6,0)=10^{18}$，$a,b$只需要考虑$[0,10^6]$。

点击展开完整代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/* Fufffh */
#include <bits/stdc++.h>
using namespace std;
using i32 = int32_t; using i64 = int64_t; using i128 = __int128_t;
using u32 = uint32_t; using u64 = uint64_t; using u128 = __uint128_t;

constexpr int V = 1'000'000;

i64 calc(i64 a, i64 b) { return a * a * a + a * a * b + a * b * b + b * b * b; }

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

    i64 n, ans = numeric_limits<i64>::max();
    cin >> n;
    for (int a = 0; a <= V; a++) {
        int l = 0, r = V, p = V;
        while (l <= r) {
            int mid = l + r >> 1;
            if (calc(a, mid) >= n) {
                p = mid;
                r = mid - 1;
            }
            else l = mid + 1;
        }
        ans = min(ans, calc(a, p));
    }
    cout << ans << '\n';
    return 0;
}

枚举$a$需要$O(V)$，每次二分需要$O(\log V)$，总时间复杂度为$O(V\log V)$，空间复杂度为$O(1)$。

这道题还有双指针做法，但二分更直接，也更适合观察“枚举一个变量，二分另一个变量”的结构。

例题五：AtCoder ABC023 D 射击王

题目链接：AtCoder ABC023 D 射击王

第$i$个气球初始高度为$H_i$，每秒上升$S_i$。从第$0$秒开始，每秒只能击破一个气球。得分是所有气球被击破时高度的最大值，要求最小化这个得分。

假设最大高度不能超过$X$。如果$X<H_i$，第$i$个气球在第$0$秒就已经超过限制，直接不可行。

否则，这个气球最晚可以在下面的时刻击破：

$$
d_i=\left\lfloor\frac{X-H_i}{S_i}\right\rfloor
$$

问题变成：每个任务需要一秒，并且有各自的截止时间$d_i$，能否安排完全部任务？

把截止时间从小到大排序。第$i$个任务使用从$0$开始的时间$i$，因此必须满足：

$$
d_i\ge i
$$

$X$越大，每个截止时间都不会减小，所以“能否完成”具有单调性。我们要找第一个可行的$X$。

上界可以取：

$$
\max_{1\le i\le n}\left(H_i+S_i(n-1)\right)
$$

因为任何气球最晚都能在第$n-1$秒被击破，这个上界一定可行。

点击展开完整代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
/* Fufffh */
#include <bits/stdc++.h>
using namespace std;
using i32 = int32_t; using i64 = int64_t; using i128 = __int128_t;
using u32 = uint32_t; using u64 = uint64_t; using u128 = __uint128_t;

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

    int n;
    cin >> n;
    vector<i64> h(n), s(n), d(n);
    i64 r = 0;
    for (int i = 0; i < n; i++) {
        cin >> h[i] >> s[i];
        r = max(r, h[i] + s[i] * (n - 1));
    }

    auto check = [&](i64 x) {
        for (int i = 0; i < n; i++) {
            if (x < h[i]) return false;
            d[i] = (x - h[i]) / s[i];
        }
        sort(d.begin(), d.end());
        for (int i = 0; i < n; i++) if (d[i] < i) return false;
        return true;
    };

    i64 l = 0, ans = r;
    while (l <= r) {
        i64 mid = l + r >> 1;
        if (check(mid)) {
            ans = mid;
            r = mid - 1;
        }
        else l = mid + 1;
    }
    cout << ans << '\n';
    return 0;
}

单次判定需要排序，时间复杂度为$O(n\log n)$。设答案范围为$V$，总时间复杂度为$O(n\log n\log V)$，空间复杂度为$O(n)$。

例题六：AtCoder ABC034 D 食盐水

题目链接：AtCoder ABC034 D 食盐水

有$n$瓶盐水，第$i$瓶重量为$w_i$，浓度为$p_i$。选择恰好$k$瓶混合，求能够得到的最大浓度。

直接比较不同组合的平均浓度很麻烦。假设目标浓度为$x$，第$i$瓶盐水中盐的质量与目标含盐量之差为：

$$
w_i p_i-w_i x=w_i(p_i-x)
$$

如果能够选择$k$瓶，使贡献和不小于$0$：

$$
\sum w_i(p_i-x)\ge 0
$$

就说明这$k$瓶混合后的浓度至少为$x$。

为了让贡献和尽可能大，每次取最大的$k$项即可。$x$越大，每一项贡献越小，因此可行浓度集中在左侧，可以实数二分最大的可行$x$。

点击展开完整代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
/* Fufffh */
#include <bits/stdc++.h>
using namespace std;
using i32 = int32_t; using i64 = int64_t; using i128 = __int128_t;
using u32 = uint32_t; using u64 = uint64_t; using u128 = __uint128_t;

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

    int n, k;
    cin >> n >> k;
    vector<double> w(n), p(n), a(n);
    for (int i = 0; i < n; i++) cin >> w[i] >> p[i];

    auto check = [&](double x) {
        for (int i = 0; i < n; i++) a[i] = w[i] * (p[i] - x);
        sort(a.rbegin(), a.rend());
        double sum = 0;
        for (int i = 0; i < k; i++) sum += a[i];
        return sum >= 0;
    };

    double l = 0, r = 100;
    for (int t = 1; t <= 100; t++) {
        double mid = (l + r) / 2;
        if (check(mid)) l = mid;
        else r = mid;
    }
    cout << fixed << setprecision(10) << l << '\n';
    return 0;
}

设固定循环次数为$T$，每次判定需要排序，总时间复杂度为$O(Tn\log n)$，空间复杂度为$O(n)$。这里$T=100$，可以视为常数。

这道题的关键不是浮点数，而是把“加权平均值至少为$x$”转换成“选出的贡献和不小于$0$”。

例题七：Codeforces 2219B2 Unique Values

题目链接：Codeforces 2219B2 Unique Values

这是一道交互题。存在一个长度为$2n+1$的隐藏数组，数值范围为$1$到$n$。其中一个值出现三次，其余值均出现两次，需要找出出现三次的值所在的三个位置。

一次查询选择下标集合$S$，交互器返回集合中“恰好出现一次的值”的数量，记为$ask(S)$。

设某个普通值在$S$中出现$c$次。由于它在整个数组中只出现两次，$c$只可能为$0,1,2$。它对集合大小和查询答案的奇偶性贡献始终相同：

$c$ 对$\lvert S\rvert$的贡献 对$ask(S)$的贡献
$0$ $0$ $0$
$1$ $1$ $1$
$2$ $0$ $0$

特殊值可能在$S$中出现$0,1,2,3$次。前三种情况仍然相同，只有三个位置全部进入$S$时，它对$\lvert S\rvert$贡献奇数$3$，对$ask(S)$却贡献$0$。

所以：

$$
ask(S)\bmod 2\ne \lvert S\rvert\bmod 2
$$

当且仅当$S$包含三个目标位置。

设目标位置从小到大为$x<y<z$。

第一次令$S=[1,mid]$。当$mid<z$时，前缀没有包含全部三个位置；当$mid\ge z$时，三个位置全部进入前缀，因此可以二分得到$z$。

找到$z$后，令：

$$
S=[1,mid]\cup{z}
$$

并在$[1,z-1]$内二分，就能找到$y$。最后固定加入$y,z$，在$[1,y-1]$内二分得到$x$。

因为$2n+1\le 2001$：

$$
\left\lceil\log_2 2001\right\rceil=11
$$

三次二分最多使用$3\times11=33$次查询，正好满足限制。

点击展开原交互版本代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
/* Fufffh */
#include <bits/stdc++.h>
using namespace std;
using i32 = int32_t; using i64 = int64_t; using i128 = __int128_t;
using u32 = uint32_t; using u64 = uint64_t; using u128 = __uint128_t;

int ask(const vector<int> &s) {
    cout << "? " << s.size();
    for (int x : s) cout << ' ' << x;
    cout << endl;
    int ans;
    cin >> ans;
    if (ans == -1) exit(0);
    return ans;
}

int get(int r, const vector<int> &ex) {
    int l = 1, ans = -1;
    while (l <= r) {
        int mid = l + r >> 1;
        vector<int> s(mid);
        iota(s.begin(), s.end(), 1);
        for (int x : ex) s.push_back(x);
        int res = ask(s);
        if ((res & 1) ^ ((int)s.size() & 1)) {
            ans = mid;
            r = mid - 1;
        }
        else l = mid + 1;
    }
    return ans;
}

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

    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        int z = get(2 * n + 1, {});
        int y = get(z - 1, {z});
        int x = get(y - 1, {y, z});
        cout << "! " << x << ' ' << y << ' ' << z << endl;
    }
    return 0;
}

这道题的查询结果本身并不单调。真正被二分的是“当前前缀是否已经包含全部目标位置”这个经过奇偶性转换的布尔条件。

总结与常见问题

怎样判断一道题能否二分？

可以依次问三个问题：

  1. 搜索对象是什么：下标、答案、时间、长度还是某个变量？
  2. 给定一个候选值以后，能否快速判断它位于答案左侧还是右侧？
  3. 这个判断是否只会改变一次？

第三点最重要。如果判定结果出现 true、false、true 这样的反复变化，普通二分就不成立。

常见错误

没有证明单调性

“答案越大越好”不等于 check(x) 单调。必须说明$x$增大以后，原来可行的方案是否仍然可行，或者原来不可行的限制是否仍然无法满足。

二分方向写反

寻找第一个 true 时，条件成立要继续向左：

1
2
ans = mid;
r = mid - 1;

寻找最后一个 true 时，条件成立要继续向右：

1
2
ans = mid;
l = mid + 1;

初始范围没有包含答案

如果$r$小于真实答案，无论模板是否正确都找不到结果。答案范围应该通过数据限制或一个显然可行的方案推出，不能只凭感觉写一个很大的常数。

check 内部发生溢出

二分答案时，mid 往往还要参与乘法。例如计算制造 mid 件物品的费用，即使最终答案能够放入 i64，中间乘积也可能提前溢出。

可以在累计达到限制后提前返回，或者在确实需要时使用 i128。

把等号放错一侧

题目要求“至少达到$h$”时，通常使用$sum\ge h$；要求“严格小于$x$”时，等号应当归入另一侧。一个等号就可能让最终答案相差$1$。

只分析了二分次数

二分只会调用$O(\log V)$次 check。如果一次判定需要$O(n\log n)$，总复杂度就是$O(n\log n\log V)$，而不是$O(\log V)$。

实数二分精度不足

使用 eps 时，计算精度应当严于输出误差；使用固定次数时，通常循环$80$到$100$次。不要让停止条件刚好等于题目允许的误差，否则浮点运算本身的误差可能影响最终结果。

复杂度分析

类型 单次判定 二分次数 总时间复杂度
有序数组边界 $O(1)$ $O(\log n)$ $O(\log n)$
整数二分答案 $O(T)$ $O(\log V)$ $O(T\log V)$
实数二分 $O(T)$ 固定$K$次，或$O\left(\log\dfrac{V}{\varepsilon}\right)$ $O(KT)$，或$O\left(T\log\dfrac{V}{\varepsilon}\right)$
枚举一维、二分一维 $O(1)$ 外层$A$次、内层$O(\log B)$ $O(A\log B)$
三次交互二分 每次一次查询 $3\lceil\log_2 n\rceil$ $O(\log n)$次查询