二分记账法与二分答案

1 传统二分的思维痛点

在前面的《二分查找》中，我们学习了基于分界点判定的 while (l < r) 模板。但在实际做题和教学中，许多同学在面对复杂的最优化问题（二分答案）时，常常遇到以下困惑：

边界死循环：中点偏向与端点更新不对称（例如把 l = mid 和 mid = (l+r)/2 混用导致区间长度为 2 时死循环）；
虚拟哨兵的负担：为了处理无解情况，常常需要在序列末尾强行伪造一个无穷大元素（开到 $n+1$ ）；
求最大值时思维割裂：当问题变成“求满足条件的最大值”时，不得不去反向思考“找第一个不合法的”，二分出结果后再强行“减 1”；
方案数据被抛弃：二分判定（check）过程中明明已经找到了合法的方案参数（如最佳切分点、起点位置），但二分退出后只剩下一个数值，不得不重新写一次扫描来还原方案。

为了彻底消除这些心智负担，本篇介绍一种更加通用、自然、零边界陷阱的实现模式——闭区间 while (l <= r) + 随手记账法。

2 核心模型：闭区间搜索 + 随手记账

思考模型只有简单的两句话：

搜索区间永远是真实的闭区间 $[l, r]$ ：初始就是 $[1, n]$ ，不需要任何多余的哨兵；
只要当前 $mid$ 合法，毫不犹豫立即“装进口袋记账”（ans = mid）；接着根据贪心目标，将区间推向未知的更有希望侧！

具体执行逻辑如下：

记账变量初值：设置 int ans = -1;（或根据业务设定无解标记），代表“目前为止尚未发现任何合法解”；
循环条件：while (l <= r)，只要闭区间内还有未排查的元素就继续；
检验中点：取 $mid = (l + r) / 2$ ：
- 若 $check(mid)$ 成立（当前可行）： $mid$ 已经是一个有效的位置了！立刻记账：ans = mid;；
  - 若求最小值 / 最左解：更左边可能还有，贪心向左缩小范围：r = mid - 1;
  - 若求最大值 / 最右解：更右边可能还有，贪心向右扩大范围：l = mid + 1;
- 若 $check(mid)$ 不成立（不可行）： $mid$ 及其对应的一侧全军覆没，果断收缩搜索空间（l = mid + 1 或 r = mid - 1）；
循环退出时：搜索区间被完全排查完毕（ $l > r$ ），口袋里的 ans 必然是最优解！若 ans 仍为 $-1$ ，说明全空间均无解。

3 完整代码实现

下面的代码展示了在同一个闭区间记账体系下，如何以完全对称的逻辑实现求下界（最左解）与求上界（最右解 / 二分答案）：

#include <iostream>
using namespace std;

const int maxn = 1e5 + 5;
int a[maxn];
int n, m;

// 模型 A：寻找第一个 >= val 的位置（最左解 / 最小值模型）
// 在闭区间 [l, r] 上搜索，未找到返回 -1
int bs_find_first_ge(int l, int r, int val) {
    int ans = -1; // 记账变量：初始为 -1 表示未找到

    while (l <= r) {
        int mid = (l + r) / 2;
        if (a[mid] >= val) {
            ans = mid;     // mid 满足要求，立即记账！
            r = mid - 1;   // 贪心向左缩小范围，寻找更靠前的解
        } else {
            l = mid + 1;   // mid 及左侧均过小，向右半区间搜索
        }
    }

    return ans; // 退出时 ans 必为最靠左的合法位置
}

// 模型 B：寻找最后一个 <= val 的位置（最右解 / 最大值模型，二分答案常用）
// 在闭区间 [l, r] 上搜索，未找到返回 -1
int bs_find_last_le(int l, int r, int val) {
    int ans = -1;

    while (l <= r) {
        int mid = (l + r) / 2;
        if (a[mid] <= val) {
            ans = mid;     // mid 满足要求，立即记账！
            l = mid + 1;   // 贪心向右扩大范围，寻找更靠后的解
        } else {
            r = mid - 1;   // mid 及右侧均过大，向左半区间搜索
        }
    }

    return ans; // 退出时 ans 必为最靠右的合法位置
}

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

    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    for (int i = 1; i <= m; i++) {
        int num;
        cin >> num;
        int pos = bs_find_first_ge(1, n, num);
        if (pos == -1) {
            cout << "not found\n";
        } else {
            cout << a[pos] << " " << pos << "\n";
        }
    }

    return 0;
}

4 理论总结与双向模型

定义1 二分性（单调谓词分割）

设搜索空间为全序集合 $X$ ，给定判定谓词 $check(x) \in \{0, 1\}$ 。如果序列在 $check$ 的映射下呈现分段单调的特性，则称该问题具备二分性。

最常见的两种形态如下：

形态一（先 0 后 1，求第一个可行解 / 最小值模型）：
$\color{blue}{\underbrace{0, 0, \cdots, 0}_{check = 0}},\quad \color{red}{\underbrace{1, 1, \cdots, 1}_{check = 1}}$
特征：越大越容易满足要求，求满足要求的最小位置。
形态二（先 1 后 0，求最后一个可行解 / 最大值模型，即二分答案）：
$\color{red}{\underbrace{1, 1, \cdots, 1}_{check = 1}},\quad \color{blue}{\underbrace{0, 0, \cdots, 0}_{check = 0}}$
特征：越小越容易满足要求，求满足要求的最大位置。

定理1 闭区间随手记账二分法则

在闭区间 $[l, r]$ 上统一使用 while (l <= r)，维护记账变量 ans。根据最优化目标，仅需对称调整合法时的试探方向：

4.1 模型 A：找满足条件的最小值（最左端点）

int ans = -1; // 初始为无解哨兵
while (l <= r) {
    int mid = (l + r) / 2;
    if (check(mid)) {
        ans = mid;    // 合法，立即记账！
        r = mid - 1;  // 贪心向左缩小，寻找更小解
    } else {
        l = mid + 1;  // 不合法，向右收缩
    }
}

4.2 模型 B：找满足条件的最大值（最右端点，二分答案）

int ans = -1; // 初始为无解哨兵
while (l <= r) {
    int mid = (l + r) / 2;
    if (check(mid)) {
        ans = mid;    // 合法，立即记账！
        l = mid + 1;  // 贪心向右冲刺，寻找更大解
    } else {
        r = mid - 1;  // 不合法，向左收缩
    }
}

说明记账法相比传统分界二分的 3 大优势

彻底告别死循环：循环体内永远对称地使用 l = mid + 1 与 r = mid - 1，闭区间长度严格减小，数学上保证在 $\lfloor \log_2(r - l + 1) \rfloor + 1$ 步内必然退出；
零差一边界心智负担：搜索空间就是真实的业务区间 $[l, r]$ ，无需在末尾制造 $\infty$ 哨兵，也无需在求最大值时反向“减 1”；
现场打包方案参数：在 check(mid) 成功时，若检验过程产出了伴随方案（如合法区间的起始坐标、分割方案），可直接在 if (check(mid)) 块内就地存下，避免二分结束后再度线性扫描。

5 严格的数学正确性证明

开始证明: $\cal{Proof}.$

本节通过循环不变量（Loop Invariant）与有限步终止性，严格证明基于闭区间 while (l <= r) 与随手记账法的二分查找/二分答案算法的正确性。

设搜索空间为整数闭区间 $[L, R]$ ，判定谓词为 $check(x) \in \{0, 1\}$ 。定义可行解集合为：

S = \{ x \in [L, R] \mid check(x) = 1 \}

以**求最小可行解（找最左端点）**为例：若 $S \neq \varnothing$ ，其理论最优解记为 $x^* = \min(S)$ ；若 $S = \varnothing$ ，则无解。（求最大可行解的证明完全对称）

我们要证明：算法执行完毕后返回的 ans 满足：

ans = \begin{cases} x^*, & S \neq \varnothing \\ -1, & S = \varnothing \end{cases}

5.1 第一部分：有限步终止性证明（绝不死循环）

设任意一轮循环开始前，当前候选闭区间为 $[l, r]$ ，其长度为 $W = r - l + 1$ 。循环条件为 $l \leqslant r$ ，即 $W \geqslant 1$ 。

计算中点 $mid = \lfloor (l + r) / 2 \rfloor$ 。由下取整除法性质，显然有：
$l \leqslant mid \leqslant r$
在循环体内，分支转移只有两种情况：
- 分支一（ $check(mid) = 1$ ）：新区间右端点变为 $r' = mid - 1$ ， $l' = l$ 。新区间长度为：
  $W' = r' - l' + 1 = (mid - 1) - l + 1 = mid - l \leqslant r - l = W - 1$
- 分支二（ $check(mid) = 0$ ）：新区间左端点变为 $l' = mid + 1$ ， $r' = r$ 。新区间长度为：
  $W' = r' - l' + 1 = r - (mid + 1) + 1 = r - mid \leqslant r - l = W - 1$
在两种分支下，均有：
$W' \leqslant \lfloor \frac{W}{2} \rfloor < W$

每轮迭代闭区间长度严格减小，且至少减少 $1$ 。由于初始区间长度 $R - L + 1$ 为有限整数，算法经过至多 $\lfloor \log_2(R - L + 1) \rfloor + 1$ 次循环后，必有 $W' \leqslant 0$ （即出现 $l > r$ ）。

因此，循环必然在有限步内收敛终止，绝不可能发生死循环。 $\quad\square$

5.2 第二部分：正确性证明（循环不变量归纳法）

定义循环进入与保持的循环不变量 $I$ ：

已发现解的合法性（Soundness）：若 $ans \neq -1$ ，则必有 $check(ans) = 1$ （即 $ans \in S$ ），且 $ans$ 是迄今为止算法探测过的所有可行解中的最小值；
最优解包含性（Completeness）：若存在比当前 $ans$ 更优的解 $x^*$ （即 $x^* < ans$ ；或当 $ans = -1$ 时 $x^*$ 存在），则必有 $x^* \in [l, r]$ 。换言之，任何严格优于当前已知最优解的候选，绝未被排除在当前闭区间 $[l, r]$ 之外。

下面使用数学归纳法证明不变量 $I$ 在循环各阶段均成立：

1. 初始化（循环开始前）

初始时 $l = L, r = R, ans = -1$ ；
$ans = -1$ ，不变量 (1) 空真成立；
若 $S \neq \varnothing$ ，显然 $x^* = \min(S) \in [L, R] = [l, r]$ ，不变量 (2) 成立。初始状态下不变量成立。

2. 状态保持（归纳递推）

假设某轮循环开始时，不变量 $I$ 成立。取中点 $mid = \lfloor (l + r) / 2 \rfloor$ ：

情况 1： $check(mid) = 1$ （ $mid \in S$ ）
- 代码执行： $ans' = mid,\; r' = mid - 1,\; l' = l$ ；
- 关于不变量 (1)：由于 $mid \in S$ ，且由归纳假设此前所有合法解均 $\geqslant mid$ （更左侧的数此前未被验证过），因此新记录的 $ans'$ 依然是所有已见解中最小者，不变量 (1) 保持成立；
- 关于不变量 (2)：由单调性，对所有 $j \geqslant mid$ ，均有 $check(j) = 1$ 。这些位置的合法解都不可能比 $mid$ 更小（更靠左）。因此，若存在比 $ans' = mid$ 更优的解 $x^*$ ，它必须严格满足 $x^* < mid$ 。结合原不变量 $x^* \in [l, r]$ ，必然有：
  $x^* \in [l, mid - 1] = [l', r']$
  更优解完好地保留在新闭区间 $[l', r']$ 内，不变量 (2) 保持成立。
情况 2： $check(mid) = 0$ （ $mid \notin S$ ）
- 代码执行： $l' = mid + 1,\; r' = r$ ， $ans$ 保持不变；
- 关于不变量 (1)： $ans$ 未发生变动，不变量 (1) 自然保持；
- 关于不变量 (2)：由单调性，对所有 $i \leqslant mid$ ，均有 $check(i) = 0$ ，即闭区间 $[l, mid]$ 内的所有数均不属于 $S$ ，它们绝不可能是可行解。因此，若存在合法解 $x^* \in [l, r]$ ，它必须严格满足 $x^* > mid$ 。故必然有：
  $x^* \in [mid + 1, r] = [l', r']$
  被剔除的区间 $[l, mid]$ 绝无错杀最优解的可能，最优解依然完整落在新闭区间 $[l', r']$ 中，不变量 (2) 保持成立。

3. 循环终止（最终判定）

循环退出时，必然满足 $l > r$ ，即搜索空间变为空区间 $[l, r] = \varnothing$ 。

由不变量 (2)，若存在严格优于当前 $ans$ 的解 $x^*$ ，则必有 $x^* \in [l, r] = \varnothing$ ，产生矛盾！因此绝不存在任何严格优于 $ans$ 的可行解：

若整个过程中从未更新过 $ans$ （依然为初值 $-1$ ），由不变量 (2) 知原集合 $S = \varnothing$ ，不存在任何可行解，返回 $-1$ 正确；
若 $ans \neq -1$ ，由不变量 (1) 知 $ans \in S$ ，且不存在比它更小的可行解，因此必然有 $ans = x^*$ 。

证明完毕. $\cal{Q.E.D}$

6 经典应用场景

掌握了“随手记账二分法则”，所有二分问题都迎刃而解：

基本查找问题：
- 第一个 $\geqslant x$ 的位置（求下界，合法时向左探 r = mid - 1）；
- 最后一个 $\leqslant x$ 的位置（求上界，合法时向右探 l = mid + 1）；
- 统计某个数 $x$ 的出现次数（上界下标 $-$ 下界下标 $+ 1$ ）。
二分答案（最优化问题）：
- 求最大值（如“最多改 $k$ 个 0 的最长连续段”）：可行时记账 best = mid，并贪心向右探寻更大解 l = mid + 1；
- 求最小值（如“最大值最小的切分代价”）：可行时记账 best = mid，并贪心向左试探更小解 r = mid - 1。

7 练习题目

CF 660C Hard Process（二分最长窗口 + 前缀和验证，随手记录起始位置）
luogu P1083 [NOIP2012 提高组] 借教室（二分答案 + 差分数组）
luogu P2678 [NOIP2015 提高组] 跳石头（二分答案求最小值最大）
luogu P1314 [NOIP2011 提高组] 聪明的质监员（二分参数求绝对差最小）
luogu P1868 饥饿的奶牛（二分查找转移前驱 + DP）
poj 3273 Monthly Expense（经典序列划分最值问题）
poj 3258 River Hopscotch（移走岩石求最短距离最大）

8 相关题解

暂无相关题解