二分查找

整数二分

右边界

如图：x为所需的边界,绿色范围为满足的区域，红色范围为不满足的区域

如何一直二分找到x呢

先设置一个mid=(l+r)/2;

判断一下mid是否符合要求；

如果结果符合，mid在x的左半边；调整区间为[mid,r],//l=mid

反之，调整区间为[l,mid-1];//r=mid-1;

如此循环下去直到l==r,此时x==l==r;

但需注意寻找右边界时容易碰到死循环。

例如当l=r-1，结果刚好符合时，此时mid=l，如此一直循环下去。所以

我们一般改为mid=（r+l+1）/2；

这时找到的为最右边的那个边界

左边界

如图：

先设置一个mid=(l+r)/2;

判断一下mid是否符合要求；

如果结果符合，mid在x的右半边；调整区间为[l,mid];//r=mid;

反之，调整区间为[mid+1,r];//l=mid+1;

如此循环下去直到l==r,此时找到的为最左边的边界

实数二分

第一种当r-l<1e-6时，认为找到了目标值

//根据题目的要求，一般要比题目的精度大二位

eg:求一个数的开方

double x;

scanf("%d",&x);

double l=0,r=x;

while(r-l>1e-6)

{double mid=r+l>>1;

if(mid*mid>=x)r=mid;

}

第二种通过循环迭荡，一直在某个数的范围减小间隔。

for(int i=0 ;i<100;i++)

{

double mid=r+l>>1;

if(mid*mid>=x) r=mid;

}