针对一个从l,r的序列,mid = (l+r)/2, 比较mid位置和x的大小,不断更新(l,r)来寻找x
模板一:(寻找x的左边界)
即判断mid>=x为true时r=mid;反之则l=mid+1;代码如下:
int bsearch_1(int l, int r)
{
while (l < r)
{
int mid = l + r >> 1;
if (check(mid)) r = mid;
else l = mid + 1;
}
return l;
}
模板二:(寻找x的右边界)
即判断mid<=x为true时l=mid(由于次更新方式为l=mid,为了防止r=l+1时mid=l,造成的l=mid=l的死循环所以此时mid=(l+r+1)/2);反之r=mid-1;代码如下:
int bsearch_2(int l, int r)
{
while (l < r)
{
int mid = l + r + 1 >> 1;
if (check(mid)) l = mid;
else r = mid - 1;
}
return l;
}
吊龙