模板 二分法和三分法

简单的算法有时候也要仔细考量。

二分

二分常常用于在一个单调序列上（实际的，或者是抽象的）寻找答案。一般使用了二分的算法的时间复杂度都会在二分内部过程的基础之上乘上一个 $\log n$ 的因子。

整数域上的二分

二分很好写，但总是有一些坑，容易写的 TLE 或者是要额外判断。
我个人推荐（也是某本书上给出的）的一种写法是：
版本A:

while (r - l){
    int mid = (r + l + 1) >> 1;
    if (judge(mid)) l = mid;
    else r = mid - 1;
}

版本B:

while (r - l){
    int mid = (r + l) >> 1;
    if (judge(mid)) r = mid;
    else l = mid + 1;
}

这种写法的好处是最后 $l$ 和 $r$ 会回到一个数上面去，就不用担心后续特判的操作。
两种版本都是正确的，这一点可以通过归纳法证明。只是使用的对象不一样。考虑好可行域的划分问题即可。
还有一点就是：这两个版本的二分对于负数域也是行得通的。因为一般右移都是算术右移，实现的是向下取整，所以可以正常工作。（不妨考虑 $[-3,-2]$）
从代码也可以看出版本 A 划分的中点更接近左边，版本 B 划分的中点更接近右边。

实数域上的二分

比起整数域上的二分，实数域由于没有向哪里取整的问题，所以更加容易实现。只需要用一个足够小的，代表二分精度的值 $\epsilon$ 判断是否足够接近即可。

while (r - l > eps){
    double mid = (r + l) / 2;
    if (judge(mid)) r = mid;
    else l = mid;
}

或者可以迭代一定次数，获得一个相对更高的精度。

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

STL

STL 中有两个基于二分实现的函数：lower_bound 和 upper_bound。
前者返回一个迭代器，其指向给定区间内第一个大于或等于给定元素的元素。
后者返回一个迭代器，其指向给定区间内第一个大于给定元素的元素。
两者在描述上差别不大。在实践中，后者还常被用来求给定区间中，最后一个小于或等于给定元素的元素（即给定元素的前驱）。只需要将返回的迭代器 -1 即可。

三分

三分法通常被用作求某一个单峰函数的极值点（和极值）。
方便起见，我们下面讨论的都是先增后减的单峰函数 $f(x)$，先减后增的单峰函数只需要将情况对调一下即可。

实数域上的三分

我们先讨论实数域上的三分法。对于当前区间 $[l, r]$，我们取其中两个点 $m, m’(m<m’)$，并且计算 $f(m), f(m’)$。然后讨论情况：

$f(m) > f(m’)$，则极值点必定不在 $[m’, r]$ 上，因为函数在这段区间必然递减。我们就可以把区间缩小为 $[l, m’]$。
$f(m) < f(m’)$，则极值点必定不在 $[l, m]$ 上，因为函数在这段区间必然递增。我们就可以把区间缩小为 $[m, r]$。
$f(m) = f(m’)$，则极值点必定在 $[m, m’]$ 上，因为函数在这段区间的左边递增，在这段区间的右边递减。我们就可以把区间缩小为 $[m, m’]$。

这样，我们做一轮三分，就能缩短区间的长度。如果 $m, m’$ 选的足够好，那么我们做足够多轮，就可以让区间长度减小到一个比较满意的值。
实践中一般做这两点：

取 $m, m’$ 为 $[l, r]$ 的三等分点。由主定理，这样做的话三分的时间复杂度为 $O(\log n)$。
一般舍去第三种情况，而将其并入到前两者中的任意一种去。这么做的原因和二分中合并条件类似。

下面给出一个简单实现：

while (r - l > eps){
    double dis = r - l;
    double mid1 = l + dis / 3;
    double mid2 = r - dis / 3;
    if (f(mid1) > f(mid2)) r = mid2;
    else l = mid1;
}

整数域上的三分

整数域上的三分比二分要麻烦，因为可能存在多种边界问题，如果写的不好容易死循环，或者出现正确性问题。
下面给出一种建议的写法：

while (r > l){
    int mid1 = (l + r) >> 1;
    int mid2 = (mid1 + r + 1) >> 1;
    if (f(mid1) > f(mid2)) 
        r = mid2 - 1;
    else l = mid1 + 1;
}

可以通过对长度归纳证明这种写法的正确性。这种写法基本适用于所有题目，不像二分一样要考虑两种 mid 的取值。

应用：某一个神奇的函数

描述：给定一个正整数序列，求该序列中的一个子序列，使得其平均数减中位数的值最大。（CF626E）

参考资料

《算法竞赛进阶指南》
Ternary Search