我这个笨比,二分的边界还是不太懂,于是想要当做这个公式被背下来

二分有两种:
1: 找到符合条件的最小值
2: 找到符合条件的最大值

换句话也可以这样说:
1: 找到>=x的后继
2 找到<=x 的前驱
也可以这样说:
1 一个数组从左边往右边开始找 (一直找到>=x的数字,
2 一个数组从右边往左边开始找(一直找到<=x的数字)

结束条件都是l==r 也就是返回l 或者r 都是 可以的

对于第一个情况来说: int mid=l+r>>1 不加1

while(l<r)
{
    int mid=l+r>>1;
    if(check(mid)) r=mid;
    else l=mid+1;
}

对于第二个情况下:int mid=l+r+1>>1 加1

while(l<r)
{
    int mid=l+r+1>>1;
    if(check(mid)) l=mid;
    else r=mid-1;
}

这是两个板子 俺是这样记忆的

对于每一个情况

它是分成这两个区间

[     ][     ]
l     基本点      r

就是如果int mid=l+r>>1 从左边找
那么mid 只的是基本点的左边
反之,从右边找,就是基本点的右边
整数二分有边界问题,是这样的.
正确的是根据check来判断l 和r 的判断
但是菜鸡的我只知道怎么板子

如果是从左边找,就是找符合条件的最小值,那么我if判断的时候应该是让右边往左边缩小
但是这个里面mid是指的是基本点的左边,所以应该是r=mid
else 的话 肯定是l=mid+1 因为基本点事左边,所以这里面+1 就是让基本点往右边移动一下,
如果是从右边开始找,就是找符合条件的最大值,那么if判断的时候偶应该是让左边开始往右边缩写
也就是说让l移动 但是+1 让基本点往右边移动了 所以也是l=mid
else 的情况下,因为基本点事右边的那个,所以我们应该是让r落在mid-1(也就是说基本点靠左边) 这一点
上
然后这个额是板子,对于check() 函数 请记住带上>= 或者<= 让其满足 if判断后面的那句话
比如从左边开始找 的话if(check(mid)) r=mid 怎么是r=mid 的捏,就是说你找的那个mid是>=x的,让这个mid缩小
同理 从右边开始找也是一样的

例题中很多都是求什么最大值,这个就是说满足条件中的最大值,这个时候我们就应该选择 int mid=l+r+1>>1 这个板子
然后进行运算.

如果是自带的函数,就是lower_bound()和upper_bound() 前面就是从左边开始中,找到第一个>=x 的 第二个是>x的数字

(上文中的基本点是我随便想的,可能是方便描述)