0x04二分

二分法是一种随处可见却非常精妙的算法，经常能为我们打开解答问题的突破口。二分的基础的用法是在单调序列或单调函数中进行查找。因此当问题的答案具有单调性时，就可以通过二分把求解转化为判定（根据复杂度理论，判定的难度小于求解），这使得二分的运用范围变得很广泛。进一步地，我们还可以扩展到通过三分法去解决单峰函数的极值以及相关问题。

据说，只有 $10\%$ 的程序员能写对二分。二分的实现方法多种多样，但是其细节之处确实需要仔细考虑。对于整数域上的二分，需要注意终止边界、左右区间取舍时的开闭情况，避免漏掉答案或造成死循环；对于实数域上的二分，需要注意精度问题。本书讲解并通篇固定使用其中一种常见的二分实现方法，一般来说读者熟练掌握自己的一种正确写法即可。

整数集合上的二分

本书所使用的二分的写法保证最终答案处于闭区间 $[l, r]$ 以内，循环以 $l == r$ 结束，每次二分的中间值 mid 会归属于左半段与右半段二者之一。

在单调递增序列 $a$ 中查找 $\geq x$ 的数中最小的一个（即 $x$ 或 $x$ 的后继）：

while  $(1 <   r)$  { int mid  $= (1 + r) / 2$  if(a[mid]  $\Rightarrow x$  ）r  $=$  mid;else  $1 =$  mid+1;   
} return a[1];

在单调递增序列 $a$ 中查找 $\leq x$ 的数中最大的一个（即 $x$ 或 $x$ 的前驱）：

while  $(1 <   r)$  { int mid  $= (1 + r + 1) / 2$  if(a[mid]  $\Leftarrow x$  ）1  $=$  mid;else  $r =$  mid-1;   
} return a[1];

在第一段代码中，若 $a[mid] \geq x$ ，则根据序列 $a$ 的单调性，mid 之后的数会更大，所以 $\geq x$ 的最小的数不可能在 mid 之后，可行区间应该缩小为左半段。因为 mid 也可能是答案，故此时应取 $r = mid$ 。同理，若 $a[mid] < x$ ，取 $l = mid + 1$ 。

在第二段代码中，若 $a[mid] \leq x$ ，则根据序列 $a$ 的单调性，mid之前的数会更小，所以 $\leq x$ 的最大的数不可能在 mid 之前，可行区间应该缩小为右半段。因为 mid 也可能是答案，故此时应取 $l = mid$ 。同理，若 $a[mid] > x$ ，取 $r = mid - 1$ 。

如上面两段代码所示，这种二分写法可能会有两种形式：

缩小范围时， $r = \text{mid}$ ， $l = \text{mid} + 1$ ，取中间值时， $\text{mid} = (l + r) / 2$ 。
缩小范围时， $l = \text{mid}$ ， $r = \text{mid} - 1$ ，取中间值时， $\text{mid} = (l + r + 1) / 2$ 。

如果不对 $mid$ 的取法加以区分，例如第二段代码假如也采用 $mid = (l + r) / 2$ 那么当 $r - l$ 等于1时，就有 $mid = \lfloor (l + r) / 2\rfloor = l$ 。接下来若进入 $l = mid$ 分支，可行区间未缩小，造成死循环；若进入 $r = mid - 1$ 分支，造成 $l > r$ ，循环不能以 $l = = r$ 结束。因此对两个形式采用配套的 $mid$ 取法是必要的。上面两段代码所示的两个形式共同组成了这种二分的实现方法。

仔细分析这两种 $mid$ 的取法，我们还发现： $mid = (l + r) / 2$ 不会取到 $r$ 这个值， $mid = (l + r + 1) / 2$ 不会取到 $l$ 这个值。可以利用这一性质来处理无解的情况，把最初的二分区间 $[1, n]$ 分别扩大为 $[1, n + 1]$ 和 $[0, n]$ ，把 $a$ 数组的一个越界的下标包含进来。如果最后二分终止于扩大后的这个越界下标上，则说明 $a$ 中不存在所求的数。

总而言之，正确写出这种二分的流程是：

通过分析具体问题，确定左右半段哪一个是可行区间，以及mid归属哪一半段。
根据分析结果，选择“ $r = \text{mid}$ ， $l = \text{mid} + 1$ ， $\text{mid} = (l + r) / 2$ ”和“ $l = \text{mid}$ ， $r = \text{mid} - 1$ ， $\text{mid} = (l + r + 1) / 2$ ”两个配套形式之一。
二分终止条件是 $l == r$ ，该值就是答案所在位置。

本书使用的这种二分方法的优点是始终保持答案位于二分区间内，二分结束条件对应的值恰好在答案所处位置，还可以很自然地处理无解的情况，形式优美。唯一的缺点是由两种形式共同组成，需要认真考虑实际问题选择对应的形式。

也有其他的二分写法，采用“ $l = mid + 1, r = mid - 1$ ”或“ $l = mid, r = mid$ ”来避免产生两种形式，但也相应地造成了丢失在 $mid$ 点上的答案、二分结束时可行区间未缩小到确切答案等问题，需要额外加以处理，这里就不再一一讲述。

$\mathrm{C}++$ STL 中的 lower_bound 与 upper_bound 函数实现了在一个序列中二分查找某个整数 $x$ 的后继，其用法参见第 0x71 节 “ $\mathrm{C}++$ STL”。

实数域上的二分

在实数域上二分较为简单，确定好所需的精度 $eps$ ，以 $l + eps < r$ 为循环条件，每次根据在 $mid$ 上的判定选择 $r = mid$ 或 $l = mid$ 分支之一即可。一般需要保留 $k$ 位小数时，则取 $eps = 10^{-(k + 2)}$ 。

while  $(1 + 1e - 5 <   r)$  { double mid  $= (1 + r) / 2$  if(calc(mid))r  $=$  mid;else  $l =$  mid;   
}

有时精度不容易确定或表示，就干脆采用循环固定次数的二分方法，也是一种相当不错的策略。这种方法得到的结果的精度通常比设置 $eps$ 更高。

for (int i = 0; i < 100; i++) { double mid = (l + r) / 2; if (calc(mid)) r = mid; else l = mid; }

$\diamond$ 三分求单峰函数极值

有一类函数被称为单峰函数，它们拥有唯一的极大值点，在极大值点左侧严格单调上升，右侧严格单调下降；或者拥有唯一的极小值点，在极小值点左侧严格单调下降，在极小值点右侧严格单调上升。为了避免混淆，我们也称后一种为单谷函数。对于单峰或单谷函数，我们可以通过三分法求其极值。

以单峰函数 $f$ 为例，我们在函数定义域 $[l,r]$ 上任取两个点 $lmid m i d$ 与 $r m i d$ ，把函数分为三段。

若 $f(lmid) < f(rmid)$ ，则 $lmidid$ 与 $rmidid$ 要么同时处于极大值点左侧（单调上升函数段），要么处于极大值点两侧。无论哪种情况下，极大值点都在 $rmidid$ 左侧，可令 $r = rmidid$ 。
同理，若 $f(lmid) > f(rmid)$ ，则极大值点一定在 $lmid$ 右侧，可令 $l = lmid$ 。

如果我们取 $lmid m$ 与 $rmid m$ 为三等分点，那么定义域范围每次缩小 $1 / 3$ 。如果我们取 $lmid m$ 与 $rmid m$ 在二等分点两侧极其接近的地方，那么定义域范围每次近似缩小 $1 / 2$ 。通过 $\log$ 级别的时间复杂度即可在指定精度下求出极值。这就是三分法。

注意，若在三分过程中遇到 $f(lmid) = f(rmid)$ ，则无法判断定义域的左右边界如何缩小。我们在介绍单峰函数时特别强调了“严格”单调性。如果在函数中存在一段值相等的部分，三分法就不再适用。

$\diamond$ 二分答案转化为判定

一个宏观的最优化问题也可以抽象为函数，其“定义域”是该问题下的可行方案，对这些可行方案进行评估得到的数值构成函数的“值域”，最优解就是评估值最优的方案（不妨设评分越高越优）。假设最优解的评分是 $S$ ，显然对于所有 $>S$ 的值，都不存在一个合法的方案达到该评分，否则就与 $S$ 的最优性矛盾；而对于所有 $<S$ 的值，一定存在一个合法的方案达到或超过该评分，因为最优解就满足这个条件。这样问题的值域就具有一种特殊的单调性——在 $S$ 的一侧合法、在 $S$ 的另一侧不合法，就像一个在 $(- \infty, S]$ 上值为 1，在 $(S, +\infty)$ 上值为 0 的分段函数，可通过二分找到这个分界点 $S$ 。借助二分，我们把求最优解的问题，转化为给定一个值 $mid$ ，判定是否存在一个可行方案评分达到 $mid$ 的问题。接下来我们通过一个经典的例子理解上述概念。

有 $N$ 本书排成一行，已知第 $i$ 本的厚度是 $A_{i}$ 。

把它们分成连续的 $M$ 组，使 $T$ 最小化，其中 $T$ 表示厚度之和最大的一组的厚度。

题目描述中出现了类似于“最大值最小”的含义，这是答案具有单调性，可用二分转化为判定的最常见、最典型的特征之一。如果我们以“把书划分为 $M$ 组的方案”作为定义域，“厚度之和最大的一组的厚度”作为评分（即值域），需要最小化这个厚度值，也就是评分越小越优。相应地，假设最终答案为 $S$ ，因为 $S$ 的最优性，如果要求每组的厚度都 $< S$ ，那么这 $M$ 组一定不能容纳这些书，可能需要更多的组才能把书分完，也就意味着对于本题的限制条件不存在可行的分书方案。如果每组的厚度可以 $> S$ ，那么一定存在一种分书方案使得组数不会超过 $M$ 。最优解就处于分书可行性的分界点上。

// 把 $n$ 本书分成 $m$ 组, 每组厚度之和 $< =$ size, 是否可行

bool valid(int size) { int group  $= 1$  rest  $=$  size; for (int i  $= 1$  ;i  $\Leftarrow$  n;i++) { if (rest  $\Rightarrow$  a[i]) rest  $\equiv$  a[i]; else group++,rest  $=$  size -a[i]; } return group  $<   =$  m;   
}   
int main() { //二分答案，判定“每组厚度之和不超过二分的值”时 //能否在m组内把书分完 int  $l = 0$  ，r  $=$  sum_of.ai; while  $(1 <   r)$  { int mid  $= (1 + r)$  /2; if(valid(mid))r  $=$  mid;else  $l =$  mid+1; } cout<<1<<endl;   
}

【例题】Best Cow Fences POJ2018

给定一个正整数数列 $A$ ，求一个平均数最大的、长度不小于 $L$ 的子段。

二分答案，判定“是否存在一个长度不小于 $L$ 的子段，平均数不小于二分的值”。

如果把数列中每个数都减去二分的值，就转化为判定“是否存在一个长度不小于 $L$ 的子段，子段和非负”。下面我们着重来解决以下两个问题：

求一个子段，它的和最大，没有“长度不小于 $L$ ”这个限制。

无长度限制的最大子段和问题是一个经典问题，只需 $O(n)$ 扫描该数列，不断把新的数加入子段，当子段和变成负数时，把当前的整个子段清空。扫描过程中出现过的最大子段和即为所求。对这个算法不熟悉的读者建议做 To the Max(POJ1050) 这道题作为练习。

求一个子段，它的和最大，子段的长度不小于 $L$ 。

子段和可以转化为前缀和相减的形式，即设 $sum_{i}$ 表示 $A_{1} \sim A_{i}$ 的和，则有：

\max _ {i - j \geq L} \left\{A _ {j + 1} + A _ {j + 2} + \dots + A _ {i} \right\} = \max _ {L \leq i \leq n} \left\{\operatorname {s u m} _ {i} - \min _ {0 \leq j \leq i - L} \left\{\operatorname {s u m} _ {j} \right\} \right\}

仔细观察上面的式子可以发现，随着 $i$ 的增长， $j$ 的取值范围 $0 \sim i - L$ 每次只会增大 1。换言之，每次只会有一个新的取值进入 $\min\{sum_j\}$ 的候选集合，所以我们没有必要每次循环枚举 $j$ ，只需要用一个变量记录当前最小值；每次与新的取值 $sum_{i-L}$ 取 $\min$ 就可以了。

double ans  $=$  -1e10;   
double min_val  $= 1$  e10;   
for (int i  $= \mathsf{L}$  ;i  $<   = \mathsf{N}$  .i++) { min_val  $=$  min(min_val, sum[i-L]); ans  $=$  max(ans, sum[i] - min_val);

解决了问题2之后，我们只需要看一下最大子段和是不是非负数，就可以确定二分上下界的变化范围了。

请读者自己思考使用二分的前提：为什么该问题的答案具有单调性？

整道题目的参考程序如下：

double a[100001], b[100001], sum[100001];  
int main() {  
    int N, L;  
    cin >> N >> L;  
    for (int i = 1; i <= N; i++) scanf("%lf", &a[i]);  
    double eps = 1e-5;  
    double l = -1e6, r = 1e6;  
    while (r - l > eps) {  
        double mid = (l + r) / 2;  
        for (int i = 1; i <= N; i++) b[i] = a[i] - mid;  
            for (int i = 1; i <= N; i++) sum[i] = (sum[i - 1] + b[i]);  
            double ans = -1e10;  
            double min_val = 1e10;  
            for (int i = L; i <= N; i++) {  
                min_val = min(min_val, sum[i - L]);  
                ans = max(ans, sum[i] - min_val);  
            }  
        if (ans >= 0) l = mid; else r = mid;  
    }

cout << int(r * 1000) << endl; }

【例题】Innovative Business

有 $N$ 个元素, 每一对元素之间的大小关系是确定的, 关系不具有传递性。也就是说, 元素的大小关系是 $N$ 个点与 $N * (N - 1) / 2$ 条有向边构成的任意有向图。

然而，这是一道交互式试题，这些关系不能一次性得知，你必须通过不超过10000次提问，每次提问只能了解某两个元素之间的关系，把这 $N$ 个元素排成一行，使得每个元素都小于右边与它相邻的元素， $N \leq 1000$ 。

根据数学归纳法，假设前 $k - 1$ 个元素已经按要求排成一行，如果能确定第 $k$ 个元素应该放在哪一个前面，即可解决此问题。

我们可以通过这样一种二分法确定第 $k$ 个元素的位置：若第 $k$ 个元素比第 mid 个元素小，令 $r = \text{mid}$ ，否则令 $l = \text{mid} + 1$ 。二分的初始区间可设为 $[1, k]$ ，区间中的 $k$ 这个值表示放在所有 $k - 1$ 个元素之后。

可以证明二分一定可以找到一个合法的位置插入，证明如下：

如果第 $k$ 个元素比第 mid 个元素小。

继续比较 $k$ 与 $mid - 1$ 这两个元素，若第 $k$ 个元素比第 $mid - 1$ 个元素大，则 $k$ 可以插在 $mid - 1$ 与 $mid$ 之间；否则说明元素 $k$ 比元素 $mid - 1$ 小，那就再比较 $k$ 与 $mid - 2$ 这两个元素，依此类推，直到发现第 $k$ 个元素比第 1 个元素小，那就放在最前边。

如果第 $k$ 个元素比第 mid 个元素大，同理。

以上只是一个证明，我们当然不会真的去依次比较 $k$ 与每个元素①。实际上通过二分，我们每询问一次（ $k$ 与 $mid$ ），就可以把区间 $[l, r]$ 缩小一半，因此至多 $\log k$ 次询问就可以确定 $k$ 应该放在哪里。把 $N$ 个元素排成一行的总询问次数不超过 $N \log N$ 。

0x04_二分

0x04二 分