作者：yxc
链接：https://www.acwing.com/blog/content/31/
来源：AcWing著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
二分一般分为如下两类：
整数二分：
版本1：当我们将区间[l, r]划分成[l, mid]和[mid + 1, r]时，其更新操作是r = mid或者l = mid + 1;mid=l+r>>1. 计算mid时不需要加1。
版本2：当我们将区间[l, r]划分成[l, mid - 1]和[mid, r]时，其更新操作是r = mid - 1或者l = mid;mid=l+r+1>>1.此时为了防止死循环，计算mid时需要加1。
实数二分：
当我们将区间[l, r]划分成[l, mid]和[mid, r]时，其更新操作是r = mid，l = mid ;mid=l+r>>1. 结果输出l或者r都可以，因为两者非常接近。
实数二分的循环可以while（r-l>10k+2）,也可以for:1~107/o(check())
什么时候用二分：
原题是最优化问题，直接求解困难，如果增加一个条件，能否转换为判定性问题。
能否用二分，能否根据终点的情况每次都能将答案区间减半。
即将最优化问题转化为判断性问题。
整数二分查找算法模板原文：
二分模板一共有两个，分别适用于不同情况。
算法思路：假设目标值在闭区间[l, r]中， 每次将区间长度缩小一半，当l = r时，我们就找到了目标值。
版本1
当我们将区间[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;
}
版本2
当我们将区间[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;
}