二分介绍

二分查找

最早接触二分一般都是从二分查找开始，对于一串有序数列（假设单调递增），如果中间值小了就往右半边找，如果中间值大了就往左半边找。

代码如下(此处为找最后一个等于x的数，如果没有x则为大于x的第一个数)：代码为什么这么写后面会讲

int l=1,r=n;
while(l<=r){
	int mid=l+r>>1;
	if(mid<=x)l=mid+1；
	else r=mid-1;
}
cout<<r<<endl;

显然对于二分不可能只局限于二分查找，我们经常会遇到对于答案进行二分的情况，将if语句中的mid<=x换成check(mid),就是我们常见的二分模板，其实二分查找也可以通过修改check函数得到

什么情况可能会使用二分

1. 单调有序数列

2. 最大值的最小值/最小值的最大值

3. O(nlogn)的时间复杂度（logn的二分，O(n)的暴力扫一遍）

二分模板

代码部分

int l=1,r=n;
while(l<=r){
	int mid=l+r>>1;
	if(check(mid))l=mid+1；
	else r=mid-1;
}
cout<<r<<endl;

如何理解

​ 对于二分的循环部分，一直存在l<=r和l<r两种写法，但由于后者经常需要考虑是否要+1/-1，相比于前者的全部+1/-1，我还是更偏向于带等号的。

​ 分支语句的部分具体需要根据题意书写，如果符合条件的集中在左边，那想要找到第一个不符合条件的就在右边，所以l=mid+1；反之亦然。

​ 对于最后你需要的是l还是r，你可以根据你的if语句中的内容来推，显然当check符合条件的时候，l必须要变，那最后l一定是不符合条件的，而r就是符合条件的。根据二分的逼近目标原理，l和r分别是符合要求的分界线，且r=l-1。

写在最后

​ 二分答案的难点其实主要在于check函数上，如何正确的check以及如何想到可以用二分是两个难点，经常会遇到题目可以感觉有些复杂度或许比较小但是实现特别麻烦的时候可以尝试使用二分来进行处理，但是记得算一下时间复杂度。