此文介绍了普通二分查找的模板

二分查找算法模板

二分模板一共有两个，分别使用于不同情况。

算法思路：假设目标位于闭区间 [l,r] 中，每次将区间长度缩小一半，当 l=r 时，我们就找到了目标值。

版本一

当我们将区间划分成 [l,mid] 和 [mid+1,r] 时，其更新操作是 r=mid 或者 l=mid+1;计算mid时不需要加1。

C++代码模板

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;
}

当我们将区间[l,r]划分成[l,mid-1]和[mid,r]时，其更新操作是 r=mid-1或者l=mid,此时为了防止死循环，计算mid时需加1

C++代码模板

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;
}