二分的本质是边界 对于整数二分与浮点数二分有不同的模板
数组里的查找
整数二分（单个)
[整数二分] [c++]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
| int bsearch_one(int l,int r)
{
while(l<r)
{
int mid=(l+r)/2;
if(q[mid]==goal) return mid;
else if(q[mid]>goal) r=mid;
else l=mid+1;
}
return -1;
}
寻找左分界点
int bsearch_one(int l,int r)
{
while(l<r)
{
int mid=(l+r)/2;
if(q[mid]>=goal) r=mid; //右边端点不断靠左边移动
else l=mid+1;
}
if(q[l]!=goal) return -1;
return l;
}
寻找右分界点
int bsearch_one(int l,int r)
{
while(l<r)
{
int mid=(l+r+1)/2;
if(q[mid]<=goal) l=mid; //右边端点不断靠左边移动
else r=mid-1;
}
if(q[l]!=goal) return -1;
return l;
}
若不存在对应数 l是找的最近的满足check的索引
|
浮点数二分 因为没有整除 所以有严格边界
[浮点数二分(例题三次方根)] [c++]1
2
3
4
5
6
7
8
9
10
11
12
| double x；
cin>>x;
double l=0,r=x;
while(r-l>1e-8)//精度尽量大
{
double mid=(l+r)/2;
if(mid*mid>=x){
r=mid;
}else{
l=mid;//不用考虑边界
}
}
|
总之浮点数二分简单多了~
