二分问题的统一解决方案

思路来自灵茶山艾府的视频《基础算法精讲 04》。本文是学习记录，结合了我自己的思考，修改后得出这个框架。

引入#

在算法题中有时会遇到这种场景：一个问题的答案是一个整数，且一定落在某个范围内，例如只可能是 $[1, 10^9]$ 中的一个数。并且存在一个条件，对于任何小于答案的数，这个条件都不成立；对于任何大于等于答案的数，这个条件都成立。这时就可以用二分的方法来找到答案。

框架与求解#

下面用严格的语言来表达这类问题（我称为二分问题）。

存在一个函数 check，它接受一个整数 i 作为输入，check(i) 只可能等于 True 或 False。并且存在一个数 $k$，使得对于任何小于 $k$ 的整数 i，都有 check(i) == False；而对于任何大于等于 $k$ 的整数 i，都有 check(i) == True。我们现在有函数 check，需要找到这个整数 $k$，并且知道 $k$ 在 $[a, b]$ 区间内。

接下来提出一个框架来解决这个问题。

首先，从获取信息的角度来思考。在实际跑一次 check 之前，我们没有获取任何信息，这时可以认为 $[a, b]$ 之间的所有整数都处于未知状态。

而运行了 check(i) 之后，由于问题的性质，我们获取到的信息不只是 check(i) 本身的真假，而是一整个范围内的整数满足或者不满足条件：

如果 check(i) == False，那么 $[a, i]$ 闭区间内所有整数的 check 结果一定也都是 False；
如果 check(i) == True，那么 $[i, b]$ 闭区间内所有整数的 check 结果一定也都是 True。

定义闭区间 $[l, r]$ 为求解区间，它满足以下三条性质：

$[l, r]$ 中全是我们还不知道 check 结果的整数；
对于任何大于 $r$ 的整数，check 的结果一定是 True；
对于任何小于 $l$ 的整数，check 的结果一定是 False。

一开始 $[a, b]$ 中全是未知的，所以把求解区间初始化为 $[a, b]$，也就是定义两个变量 l、r，令 l <- a, r <- b。

然后取求解区间的中点 mid <- l + (r - l) / 2，计算 check(mid)：

如果 check(mid) == True，说明 $[mid, r]$ 都是 True，这一段从未知变为已知，因此令 r <- mid - 1；
如果 check(mid) == False，说明 $[l, mid]$ 都是 False，这一段从未知变为已知，因此令 l <- mid + 1。

这两种操作都保持了上面三条性质始终成立。然后重复取中点和上述操作，直到 $r < l$ 为止。此时求解区间为空，也就是未知的部分为空，$[a, b]$ 内每一个整数的 check 结果都已经知道了。我们的目标就是：在三条性质始终成立的前提下，把未知区间变为空。

未知区间为空之后，$r$ 一定等于 $l - 1$。此时 r 就是最后一个 False 所在的位置，l 就是第一个 True 所在的位置，题目要哪一个就返回哪一个。

写成 C++ 就是：

// 返回 [a, b] 中第一个使 check 为 true 的整数
long long first_true(long long a, long long b, auto check)
{
    long long l = a, r = b; // 求解区间 [l, r]：里面全是未知的
    while (l <= r)          // 求解区间非空
    {
        long long mid = l + (r - l) / 2;
        if (check(mid))
            r = mid - 1; // [mid, r] 都是 true
        else
            l = mid + 1; // [l, mid] 都是 false
    }
    return l; // 此时 r == l - 1
}

举例说明（可以先看这个部分）#

假设把 check 应用在下标 0 到 8 上，得到的结果分别是

$$[F, F, F, F, T, T, T, T, T]$$

那么取 l <- 0, r <- 8，计算得到 mid <- 4。

此时 check(4) == T，说明 $[4, 8]$ 区间内的每一个整数都是 T，它们从未知变成已知。执行 r <- mid - 1，得到新的未知区间 [l, r] == [0, 3]。

计算 mid <- l + (r - l) / 2，得到新的 mid == 1。此时 check(1) == F，说明 $[0, 1]$ 区间均为 F。执行 l <- mid + 1，新的未知区间为 [l, r] == [2, 3]。

计算得到新的 mid == 2。此时 check(2) == F，说明 $[0, 2]$ 区间均为 F。执行 l <- mid + 1，新的未知区间为 [l, r] == [3, 3]。

计算得到新的 mid == 3。此时 check(3) == F，说明 $[0, 3]$ 区间均为 F。执行 l <- mid + 1，新的未知区间为 [l, r] == [4, 3]，即空区间。

计算结束。此时 l == 4, r == 3：l 就是第一个 T 所在的位置，r 就是最后一个 F 所在的位置。

2026 年 10 月修订。 修正了例子里的笔误：原文把更新写成了 mid <- (r - 1) 和 mid <- (l + 1)，应为 r <- mid - 1 和 l <- mid + 1；原文说把 check 应用在 1 到 9 上，却又从 l <- 0, r <- 8 开始，现统一为下标 0 到 8。补充了与文字描述一一对应的 C++ 代码（需要 C++20 才能用 auto 形参）。注意 l、r 要用有符号整数：当 $a = 0$ 且 check(0) 为真时，r 会变成 $-1$，无符号类型会在这里回绕。