0x04 二分
二分的基础的用法是在单调序列或单调函数中进行查找。
因此，当问题的答案具有单调性时，就可以通过二分把求解转化为判定（根据复杂度理论，判定的难度小于求解），这使得二分的运用范围变得很广泛。
进一步地，我们还可以扩展到通过三分法去解决单峰函数的极值以及相关问题。
二分的视线方法多种多样，但是其细节之处确实需要仔细考虑。
- 对于整数域上的二分，需要注意终止边界、左右区间取舍时的开闭情况，避免漏掉答案或造成死循环；
- 对于实数域上的二分，需要注意精度问题。
整数集合上的二分
二分的写法保证最终答案处于闭区间 $[l, r]$ 以内，
循环以 $l=r$ 结束，
每次二分的中间值 $mid$ 会归属于左半段或右半段二者之一。
- 在单调递增序列 $a$ 中查找 $\geq x$ 的数中最小的一个（即 $x$ 或 $x$ 的后继）：
while (l < r) { int mid = (l + r) >> 1; if (a[mid] >= x) r = mid; else l = mid + 1; } return a[l]; - 在单调递增序列 $a$ 中查找 $\leq x$ 的数中最大的一个（即 $x$ 或 $x$ 的前驱）：
while (l < r) { int mid = (l + r + 1) >> 1; if (a[mid] <= x) l = mid; else r = mid - 1; } return a[l];
在第一段代码中，若 $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 = mid$，$l = mid + 1$，取中间值时，$mid = (l + r) » 1$。
- 缩小范围时，$l = mid$，$r = mid + 1$，取中间值时，$mid = (l + r + 1) » 1$。
如果不对 $mid$ 的取法加以区分，假如第二段代码也采用 $mid = (l + r) » 1$，
那么当 $r - l$ 等于 $1$ 时，就有 $mid = (l + r) » 1 = l$。
接下来若进入 $l = mid$ 分支，可行区间未缩小，造成死循环；
若进入 $r = mid - 1$ 分支，造成 $l > r$，循环不能以 $l = r$ 结束。
因此对两个形式采取配套的 $mid$ 取法是必要的。
上面两段代码所示的两个形式共同组成了这种二分的视线方法。
注意，我们在二分实现中采取了右移运算 $» 1$，而不是整数除法 $/ 2$。
这是因为右移运算是向下取整，而整数除法是向零取整，在二分值域包含负数时后者不能正常工作。
仔细分析这两种 $mid$ 的取法，我们还发现：
$mid = (l + r) » 1$ 不会取到 $r$ 这个值，$mid = (l + r + 1) » 1$ 不会取到 $l$ 这个值。
我们可以利用这一性质来处理无解的情况，
把最初的二分区间 $[1, n]$ 分别扩大为 $[1, n + 1]$ 和 $[0, n]$，把 $a$ 数组的一个越界的下标包含进来。
如果最后二分终止于扩大后的这个越界下标上，则说明 $a$ 中不存在所求的数。
总而言之，正确写出这种二分的流程是：
- 通过分析具体问题，确定左右半段哪一个是可行区间，以及 $mid$ 归属哪一半段；
- 根据分析结果，选择 “$r = mid, l = mid + 1, mid = (l + r) » 1$” 和 “$l = mid, r = mid - 1, mid = (l + r + 1) » 1$” 两个配套形式之一；
- 二分的终止条件是 $l == r$，该值就是答案所在位置。
本书使用的这种二分方法的优点是始终保持答案位于二分区间内，二分结束条件对应的值恰好在答案所处位置，还可以自然地处理无解的情况，形式优美。
唯一的缺点是由两种形式共同组成，需要认真考虑实际问题选择对应的形式。
也有其他的二分写法，采用 “$l = mid + 1, r = mid - 1$” 或 “$l = mid, r = mid$” 来避免产生两种形式，但也相应地造成了丢失在 $mid$ 点上的答案、二分结束时可行区间未缩小到确切答案等问题，需要额外加以处理。
C++ STL 中的 lower_bound 与 upper_bound 函数实现了在一个序列中二分查找某个整数 $x$ 的后继。
实数域上的二分
在实数域上的二分较为简单，确定好所需的精度 $eps$，以 $l + eps < r$ 为循环条件，每次根据在 $mid$ 上的判定选择 $r = mid$ 或 $l = mid$ 分支之一即可。
一般需要保留 $k$ 位小数时，则取 $eps = 10^{- (k + 2)}$。
while (l + 1e-5 < r) {
double mid = (l + r) / 2;
if (calc(mid)) r = mid; else l = mid;
}
有时精度不容易确定或表示，就干脆采用循环固定次数的二分方法，也是一种相当不错的策略。
这种方法得到的结果的精度通常比设置 $eps$ 更高。
for (int i = 0; i < 100; i++) {
double mid = (l + 1) / 2;
if (calc(mid)) r = mid; else l = mid;
}
三分求单峰函数极值
有一类函数被称为单峰函数，它们拥有唯一的极大值点，在极大值点左侧严格单调上升，右侧严格单调下降；
或者拥有唯一的极小值点，在极小值点左侧严格单调下降，在极小值点右侧严格单调上升。
为了避免混淆，我们也称后一种为单谷函数。
对于单峰函数或单谷函数，我们可以通过三分法求其极值。
以单峰函数 $f$ 为例，我们在函数定义域 $[l, r]$ 上任取两个点 $lmid$ 与 $rmid$，把函数分为三段。
- 若 $f(lmid) < f(rmid)$，则 $lmid$ 与 $rmid$ 要么同时处于极大值点左侧（单调上升函数段），要么处于极大值点两侧。无论哪种情况下，极大值点都在 $lmid$ 右侧，可令 $l = lmid$。
- 同理，若 $f(lmid) > f(rmid)$，则极大值点一定在 $rmid$ 左侧，可令 $r = rmid$。
如果我们取 $lmid$ 与 $rmid$ 为三等分点，那么定义域范围每次缩小 $1 / 3$。
如果我们取 $lmid$ 与 $rmid$ 在二等分点两侧机器接近的地方，那么定义域范围每次近似缩小 $1 / 2$。
通过 log 级别的时间复杂度即可在指定精度下求出极值。这就是三分法。
注意，我们在介绍单峰函数时特别强调了 “严格” 单调性。
若在三分过程中遇到 $f(lmid) = f(rmid)$，当函数严格单调时，令 $l = lmid$ 或 $r = rmid$ 均可。
如果函数不严格单调，即在函数中存在一段值相等的部分，那么我们无法判断定义域的左右边界如何缩小，三分法就不再适用。
二分答案转化为判定
一个宏观的最优化问题也可以抽象为函数，其 “定义域” 是该问题下的可行方案，对这些可行方案进行评估得到的数值构成函数的 “值域”，最优解就是评估值最优的方案（不妨设评分越高越优）。
假设最优解的评分时 $S$，显然对于 $\forall x > S$，都不存在一个合法的方案达到 $x$ 分，否则就与 $S$ 的最优性矛盾；
而对于 $\forall x \leq S$，一定存在一个合法的方案达到或超过 $x$ 分，因为最优解就满足这个条件。
这样问题的值域就具有一种特殊的单调性——在 $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 <= n; i++) {
if (rest >= a[i]) rest -= a[i];
else group++, rest = size - a[i];
}
return group <= m;
}
int main() {
// 二分答案，判定 “每组厚度之和不超过二分的值” 时
// 能否在m组内把书读完
int l = max_of_ai, r = sum_of_ai;
while (l < r) {
int mid = (l + r) / 2;
if (valid(mid)) r = mid; else l = mid + 1;
}
cout << l << endl;
}