（ACM模板）二分查找

二分是一个比较大的概念，广义上把东西(可能是问题，区间等等)一分为二都是二分。

这里讲二分查找。

据说只有10%的程序员能写对二分。虽然二分是一个简单的算法。但是其变化和细节却并不简单。

整数二分：

因为mid取整的问题，如果不细心有可能会死循环。

所以写二分查找需要仔细考虑 答案在开/闭区间？mid向上/下取整？循环结束条件？这些选择的取舍不同会导致二分的写法不同，没有说必须哪一种是正确的。掌握自己喜欢的写法即可。

这里的二分保证答案必须在[L,R]闭区间，循环借宿条件为(L==R)，答案下标为 L 。

代码如下，其中细节还是值得细细琢磨。

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=100000;
int n,q,a[N],l,r; 

int main()
{
    scanf("%d",&n);
    for (int i=1;i<=n;i++) scanf("%d",&a[i]);
    sort(a+1,a+n+1);
    
    //查找满足>=q的第一个数（x或x的后继）
    //因为是>=蓑衣用向下（即L）取整
    //注意要保证答案在[L,R]区间，这里满足(a[mid]>=q)即mid在答案区间内r=mid，else即mid不在答案区间内l=mid+1舍弃mid 
    scanf("%d",&q);
    l=1,r=n;
    while (l<r) {
        int mid=l+(r-l)/2;
        if (a[mid]>=q) r=mid; else l=mid+1;
    }
    cout<<a[l];
    
    //查找满足<=q的最后一个数（x或x的前驱） 
    scanf("%d",&q);
    l=1,r=n; 
    while (l<r) {
        int mid=l+(r+1-l)/2;
        if (a[mid]<=q) l=mid; else r=mid-1; 
    }
    cout<<a[l];
    
    return 0;
} 

浮点数二分：

因为不用考虑取整的问题，所以浮点数二分相当好些。

注意精度问题就可以了。

    double eps=1e-5;
    while (l+eps<r) {
        double mid=(l+r)/2;
        if (check(mid)) l=mid; else r=mid;
    }

三分求单峰函数极值：

当这个函数可能是单调函数时(极值点在端点), 三分算法无法到达端点位置, 所以要特判一下两个端点。

int lm, rm;
while(l<r) 
{
    lm = l+(r-l)/2;
    rm = lm+(r-lm)/2;
    if(a[lm] > a[rm]) r = rm;
    else if(a[lm] == a[rm]) r=rm, l=lm;
    else l = lm;
}