二分 学习笔记

以下程序对比了lower_bound和自写函数的比较，基本上能够保证正确

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<ctime>
using namespace std;
#define ms(i,j) memset(i,j,sizeof i);
const int MAXN = 1000;
int n = 20;
int a[MAXN];
int rightans;
int cans;
int bs(int begin, int end, int x)
{
    int l = begin, r = end;
    int mid;
    while (l<r)//如果是浮点数，换成for(int i=0;i<100;i++)
    {即可
        mid = (l+r)/2;
        if (x>a[mid]) l = mid+1;
        else r = mid;
    }
    return r;
}
int main()
{
    //freopen(".in", "r", stdin); freopen(".out", "w", stdout);
    srand((int)time(0));
    for (;;) 
    {
        for (int i=0;i<n;i++) a[i] = rand()%100;
        sort(a, a+n);
        int f = rand()%100;
        rightans = lower_bound(a, a+n, f)-a;
        cans = bs(0, n, f);
        if (rightans!=cans) {printf("wrong\n"); break;} else printf("right!\n");
    }
    //fclose(stdin); fclose(stdout);
    return 0;
}