写在前面
二分是一种常用且非常精妙的算法，常常是我们解决问题的突破口。二分的基本用途是在单调序列或单调函数中做查找。因此当问题的答案具有单调性时，就可以通过二分把求解转化为判定。进一步地，我们还可以通过三分法解决单调函数的极值以及相关问题。
刷题进度
二分答案（2/4）
二分查找
问题解决进度
Q1
一、二分
二分法，在一个单调有序的集合或函数中查找一个解，每次分为左右两部分，判断在哪个部分中并调整上下界，直到找到目标元素，每次二分后都将舍弃一半的查找空间，因此效率很高。
显然，二分算法的复杂度为O(二分次数×单次判定复杂度)
……可怜的我依旧不会算复杂度QAQ……
二、二分核心代码
1.整数定义域
int work(int l,int r){int l=-INF,r=INF;//根据题目要求改变左右端点的初始值while(l<r){int mid=(l+r)>>1;if(check(mid+1)) l=mid+1;//如果符合要求就继续二分查找else r=mid;}return l; }
2.实数定义域
double work(double l,double r){//根据题目要求确定精度dltdouble mid;while(fabs(l-r)>dlt){//实数比较大小，此句相当于l<r //补充:fabs(x1)很abs(x2)都表示求绝对值，只不过x1是实数，x2是整数mid=(l+r)/2.0;if(check(mid)) r=mid;else l=mid;}return l; }
TIP：如果指定二分的次数为t，那么对于初始的求解区间长度L，算法结束后r-l的值为L/2t
三、二分法常见模型
最小值最大（或最大值最小）问题，这类双最值问题常常选用二分法求解，也就是确定答案后，配合贪心、DP等其他算法检验这个答案是否合理，将最优化问题转换为判定性问题。
【例 1】
将长度为n的序列分成最多m个连续段，求所有分法中每段和的最大值的最小是多少？
一些题目
LuoguP1024
LuoguP2678
LuoguP3957
Luogu二分答案
用具有单调性的布尔表达式求解分界点。
【例 2】
在有序数列中求数字x的排名。
一些题目
Luogu二分查找
3.代替三分
有时，对于一些单峰函数，我们可以用二分导函数的方法求解函数极值，这时通常将函数的定义域定义为整数域求解比较方便。
四、典型例题
【例 1】愤怒的牛(Bzoj 1734)
1.题目大意
已知有n间牛舍和每间牛舍的位置，现在要求一种方案使得m头牛两两之间的最小距离尽可能大，求这个最大的最小距离。
2.思路
这是一道最大值最小化的典型题目。
设C(d)表示可以安排牛的位置，并使得最近的两头牛距离≥d
那么问题就转化为了求满足C(d)的最大的d，最近的间距≥d可以看成是所有间距都≥d，因此满足C(d)的条件就是任意两头牛的位置≥d
于是可以贪心求解：
<1>对牛舍的位置x进行排序
<2>把第一头牛放入x0的牛舍
<3>如果第i头牛放入了xj的牛舍，则第i+1头牛就要放入满足xj+d≤xk的xk最小的牛舍中
对x的排序只要在开始时进行一次就可以了，每一次判断对每头牛最多进行一次处理，因此算法的时间复杂度为O(nlogn)
3.代码
咕咕咕咕咕
【例 2】Best Cow Fences(Poj 2018)
1.题目大意
给定一个长度为n的正整数序列A，求一个平均数最大的，长度≥L的子序列。
2.思路
二分答案mid，合法的条件为“存在一个长度≥L的子序列，平均数≥mid”
如果把数列中的每个数都减去二分的值，合法的条件就转化为“存在一个长度≥L的子序列，子序列每一项相加的和≥0”
接下来就是着重解决两个问题：
<1>求一个子序列，要求和最大，没有“长度≥L”的限制
无长度限制的最大子序列和问题是一个经典问题，只需O(n)扫描该数列，不断地把新的数加入子序列，当子序列的和变成负数时，把当前的整个子序列清空。扫描过程中出现的最大子序列和即为所求。
子序列和可以转化为前缀和相减的形式，即设sumi表示A1～Ai的和，则有：
maxi-j≥L{Aj+1+Aj+2+……+Ai}=maxL≤i≤n{sumi-min0≤j≤i-L{sumj}}
这个式子啥意思呀？QAQ
这个式子随着i的增长，j的取值范围0～i-L每次只会增加1。也就是说，每次只会有一个新的值进入min{sumj}的候选集合，所以没有必要每次循环枚举j次，只需要用一个变量记录当前最小值，每次与新的取值sumi-L取min就可以了。
解决了这两个问题后，我们只需要判断最大子序列和是不是非负数，就可以确定二分上下界的变化范围了。
3.代码
咕咕咕咕咕