二分与三分
二分查找
在一个单调序列中查找一个元素的算法。
一般偷懒做法：lower_bound函数直接实现。
具体实现：不断以从答案所在的区间中间划分出两个子区间，舍弃不存在答案的那一个子区间，在存在答案的那个区间继续二分。
二分答案
在所有问题的答案的集合中二分查找最优解的算法。
具体而言，就是先找出答案的范围，确定答案的集合，判断答案的单调性，并在答案的范围中进行二分，判断依据为答案是否成立或可行。
是否可以二分答案的条件：
- 答案具有单调性，即可二分性。
- 二分出的答案可以进行可行性检验。
题目特征：经常出现“最大值最小”这种诡异的说法。
推荐题目：
三分求单峰函数极值
在一个单调单峰/单谷函数中求解最值的算法。
是否可以进行三分的条件：
- 函数是单峰的
- 函数是严格单调的（即不存在一段平直的区间）
对于存在最值得一段区间([l,r])，我们取出其中的两个点(lmid)和(rmid)，使得这个区间被分成三段，对于任意的(lmid)和(rmid)，会出现以下两种情况：
- (f(lmid)<f(rmid))，此时(lmid)和(rmid)要不然都在最值右边，要不然在最值两边，由于函数是严格单调的，这样我们就可以确保([l,lmid])这一段区间是不存在最值的，舍弃它，在剩下的子区间中继续三分。
- (f(lmid)>f(rmid))，类比上面这种情况，我们舍弃([rmid,r])这段区间。
当然，(lmid)和(rmid)的值只要(lmid<rmid)且(l<lmid,r>rmid)就可以任意取，比如说取三等分点，不过有一种更优的方法。
设(lmid)和(rmid)分别是(l,r)的稍微偏离中点一点点的左边和右边的位置，这样不仅保证了函数被分为三段，又实现了每次三分近似于二分，又保证了这个三分的复杂度近似于(O(logn))。
具体实现看代码：
while(l+eps<r){//eps为精度
double lmid=(l+r)/2-eps/10,rmid=(l+r)/2+eps/10;//为了不出意外，我把eps除以了10
if(calc(lmid)<calc(rmid)) l=lmid;
else if(calc(lmid)>=calc(lmid)) r=rmid;
}
板子：