二分 学习笔记

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#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;
}
------ 本文结束 ------