本篇将介绍二分和三分算法

二分法

简介

二分查找又称折半搜索，是用于在一个有序数列中查找某一元素的算法。

方法

假设有一个升序排列数组 $a$ ，定义区间左右指针分别为 $l$ 和 $r$ , 需要查找的目标元素 $t$ 。每次取出中间数 $mid = l+r>>1$ ，如果其小于等于 $t$ ，则将 $r = mid$ ，如果其大于 $t$ ，则将 $l=mid+1$ ，直到 $l=r$ 停止计算， $l$ 或者 $r$ 就是答案。

实现

int binary_search(int t, int a[], int l, int r) {
    while(l < r){
        int mid=l+r >> 1;
        if(t <= a[mid]) r=mid;
        else l=mid+1;
    }
    return l;
}

应用

STL二分查找

实际使用中我们可以直接使用STL库的 lower_bound 和 upper_bound 分别查找第一个大于等于和小于等于 value 的数
参数分别为 first, last, value ，分别是迭代器开头，迭代器结尾，对比的值。但是使用前需保证元素单调

二分答案 or 最大值最小

对于题目需要满足以下条件：

所有可行解都在一个区间之中。
判断解的可行情况的时间复杂度不高，足够多次重复判断。
对于题目中的可行解满足一定的单调性，例如若 $x$ 可行，那么大于 $x$ 或者小于 $x$ 的解都可行，那么认为其单调。

这类应用在题目中常常会提到求 最大值最小 或者 最小值最大 又或者 在符合条件的情况下的最值 。

对其的朴素解法就是按照顺序枚举其每个值，直到第一个满足的即为答案。但是我们可以使用二分法，来更快的寻找答案，如果他符合要求则去掉符合要求但不是最值的那部分，如果不符合要求则去掉比他还不可能符合要求的那部分。最后剩下的即为符合要求的最值。

三分法

简介

二分法可以查找一个单调函数的答案，但是当我们需要查找一个 单峰/单谷函数 的极值点的时候，通常使用三分法来解决。

方法

和二分法一样，我们用三等分点 $lmid$ 和 $rmid$ 分割成三个区间，假设我们需要找到单峰数组 $a$ 的最大值，讨论四种可能性：

如果 $lmid$ 和 $rmid$ 都在极值点左侧，则 $a[lmid] < a[rmid]$ ，那么小于 $lmid$ 的值一定不是极值点
如果 $lmid$ 和 $rmid$ 分别在极值点两侧，但是 $a[lmid] <= a[rmid]$ ，那么小于 $lmid$ 的值一定不是极值点
如果 $lmid$ 和 $rmid$ 分别在极值点两侧，但是 $a[lmid] >= a[rmid]$ ，那么大于 $rmid$ 的值一定不是极值点
如果 $lmid$ 和 $rmid$ 都在极值点右侧，则 $a[lmid] > a[rmid]$ ，那么大于 $rmid$ 的值一定不是极值点

我们可以发现，两个值中较小的那个值靠外的区间，一定不是极值点，那么我们就可以将其舍弃

由于三分存在精度问题，要么当我们舍弃到无法继续舍弃的时候手动判断，要么选择舍弃精度输出近似值

实现

int ternary_search(int esp, int a[], int l, int r) {
    while(r - l > esp) {
        int lmid = l + (r-l) / 3, rmid = r - (r-l) / 3;
        if(a[lmid] < a[rmid]) l = lmid;
        else r = rmid;
    }
    return l;
}