（ACM模板）二分查找

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

这里讲二分查找。

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

整数二分：

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

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

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

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

#include<iostream>

#include<cstdio>

#include<algorithm>

using namespace std;

const int N=;

int n,q,a[N],l,r; 

int main()

{

    scanf("%d",&n);

    for (int i=;i<=n;i++) scanf("%d",&a[i]);

    sort(a+,a+n+);

    //查找满足>=q的第一个数（x或x的后继）

    //因为是>=蓑衣用向下（即L）取整

    //注意要保证答案在[L,R]区间，这里满足(a[mid]>=q)即mid在答案区间内r=mid，else即mid不在答案区间内l=mid+1舍弃mid

    scanf("%d",&q);

    l=,r=n;

    while (l<r) {

        int mid=l+(r-l)/;

        if (a[mid]>=q) r=mid; else l=mid+;

    }

    cout<<a[l];

    //查找满足<=q的最后一个数（x或x的前驱）

    scanf("%d",&q);

    l=,r=n;

    while (l<r) {

        int mid=l+(r+-l)/;

        if (a[mid]<=q) l=mid; else r=mid-;

    }

    cout<<a[l];

    return ;

}

浮点数二分：

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

注意精度问题就可以了。

    double eps=1e-;

    while (l+eps<r) {

        double mid=(l+r)/;

        if (check(mid)) l=mid; else r=mid;

    }

三分求单峰函数极值：

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

int lm, rm;

while(l<r)

{

    lm = l+(r-l)/;

    rm = lm+(r-lm)/;

    if(a[lm] > a[rm]) r = rm;

    else if(a[lm] == a[rm]) r=rm, l=lm;

    else l = lm;

}

巴特西

（ACM模板）二分查找

最新文章

热门文章