二分

发表于

二分二分，一分为二，分而取之

整数集合上的二分

单调递增序列a

初始l=1,r=N

写法1

1
2
3
4
5
6
while(l<r){
    int mid=(l+r)/2;
    if(a[mid]>=x)r=mid;
    else l=mid+1;
}
return a[l];

写法2

1
2
3
4
5
6
while(l<r){
    int mid=(l+r+1)/2;
    if(a[mid]<=x)l=mid;
    else r=mid-1;
}
return a[l];
  1. 缩小范围时，r=mid,l=mid+1,取中间值 mid=(l+r)/2
  2. 缩小范围时，l=mid,r=mid-1,取中间值 mid=(l+r+1)/2

不同形式的原因在于程序除法向下取整

二分的终止条件是l=r,该值就是答案

实数域

确定精度eps

如果保留k位小数，eps=10^(-(k+2))

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

循环固定次数也可

1
2
3
4
5
for(int i=1;i<=100;++i){
    double mid=(l+r)/2;
    if(calc(mid))r=mid;
    else l=mid;
}