算法竞赛进阶指南0x04 二分
二分法是一种随处可见却非常精妙的算法，经常能为我们打开解答问题的突破口。二分的基础的用法是在单调序列或单调函数中进行查找。因此当问题的答案具有单调性时，就可以通过二分把求解转化为判定 (根据复杂度理论，判定的难度小于求解)，这使得二分的运用范围变得更广泛。进一步地，我们还可以扩展到通过三分法去解决单峰函数的极值以及相关问题。
整数集合上的二分
本篇文章所使用的二分的写法保证最终答案处于闭区间 [L,R] 以内，循环以 L = R结束，每次二分的中间值 mid 会归属于左半段与右半段二者之一。
$$ 在单调递增序列 a 中查找 \ge x 的数中最小的一个(即 x 或 x 的后继)。$$
while (l < r) {
int mid = (l + r) >> 1;
// mid = (l + r) / 2
if (a[mid] >= x) {
r = mid;
} else {
l = mid + 1;
}
}
return a[l];lower_bound：
int pos = std::lower_bound(a + 1, a + 1 + n, x) - (a + 1);
return a[pos];$$ 在单调递增序列 a 中查找 \le x 的数中最小的一个(即 x 或 x 的前驱)。$$
while (l < r) {
int mid = (l + r + 1) >> 1;
// mid = (l + r + 1) / 2
if (a[mid] <= x) {
l = mid;
} else {
r = mid - 1;
}
}
return a[l];在第一段代码中，若 a[mid] >= x，则根据序列 a 的单调性， mid 之后的数会变大，所以 >= x的最小的数不可能在 mid 之后，可行区间应该缩小为左半段。因为 mid 也可能是答案，故此时应取 R = mid。同理，若 a[mid] < x，取 L = mid + 1。
在第二段代码中，若 a[mid] <= x，则根据序列 a 的单调性，mid 之前的数会变小，所以<= x 的最大的数不可能在 mid 之前，可行区间应该缩小为右半段。因为 mid 也可能是答案，故此时应取 L = mid。同理，若 a[mid] > x，则取 R = mid - 1。