二分查找模板一共有两个，分别适用于不同的情况。
算法思路：假设目标值在闭区间[l, r]中，每次将区间长度缩小一半，当l = r时，我们就找到了目标值。
二分流程
- 确定二分边界，注意是闭区间；
- 编写二分的代码框架；
- 设计一个check(性质)：可以将区间划分为两部分，一部分满足这个性质，另一部分不满足这个性质；
- 判断一下区间如何更新；
- 如果更新方式写的是
l = mid, r = mid - 1;那么就在计算mid的时候+1.
版本1
当我们将区间[l, r] 划分成[l, mid]和[mid + 1, r]时，其更新操作是r = mid或者l = mid + 1，此时计算mid的时不需要+1。
C++代码模板
1
2
3
4
5
6
7
8
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;
}
版本2
当我们将闭区间[l, r]划分为[l, mid - 1]和[mid, r]时，其更新操作是r = mid - 1 或者l = mid，此时为了防止死循环，计算mid时需要+1。
C++代码模板
1
2
3
4
5
6
7
8
int bsearch_2(int l, int r){
while(l < r){
int mid = l + r + 1 >> 1;
if(check(mid))l = mid;
r = mid - 1;
}
return l;
}
