二分是个非常神奇的算法，可以把时间复杂度优化到 Logn ，所以二分应用还是很广的，下面总结一下二分的几种题型与例题：
一、最大化最小值、最小化最大值问题
1.基本题意：
①最大化最小值问题：n个东西分给m个人，每人至少拿x个，问x最大值。
②最小化最大值问题：n个东西分给m个人，每人至多拿x个，问x最小值。
分析：首先这种问题需要一个限制条件，而以上题目的限制条件就是要分给m个人：
所以
①：每人至少拿x个，我们假设现在x的最大值就是 p，所以当前每人至少拿p个，因为我们要考虑在最坏的情况下能不能够分m个人，所以每个人都拿p个，看此时可以分的人数是否>=m，如果>=m true，否则false。
②：每人至多拿x个，我们假设现在的x最小值就是p，所以当前每人至多拿p个，此时的最坏情况应该是都拿p个，判断一下是否<=m个人，如果小于的话则满足要求，否则则不满足要求(因为已经都尽可能的拿了还多着)
2.例题
①POJ3273&&Monthly Expense
中文题意：给你n个数，让分成m组，每组必须是连续的一些数，求每组的和的最大值最小。
分析：
One：最小化最大值问题，首先分析制约因素-m，然后思考判断条件：假设当前的和是最大，以此和分组可以分多少组呢？如果当前组数>m,则返回false，否则返回true。
Two：为什么可以这么想呢？在这里解释一下单调性：如果我们以当前和为依据分组，如果大于m组，说明当前的和太小，我们需要增大当前最大和，也就是当前的最大和不满足分m组的条件。否则当前最大和满足条件但是不一定是最小，所以我们向小寻找发现有没有更优解(即一个为可行解，一个为最优解)。
所以代码也就写出来了：
int n,m;
int num[maxn];
bool judge(int x)
{
for(int i=1;i<=n;i++)
if(num[i]>x) return false;//既然假设了当前是最大和，那么如果有一个数大于当前的话，这个最大和绝对不成立，因为无论怎么分，这个数也大于当前最大和
int tot=1,sum=0;//初始tot=1！！！
for(int i=1;i<=n;i++)//求最多可以连续分多少段
{
sum+=num[i];
if(sum>x)//sum>x就不可以了
{
tot++;
sum=num[i];//看看与后面是否可以
}
}
if(tot>m) return false;
return true;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d",&num[i]);
int l=0,r=INF;
int ans;
while(l-r<=0)//二分最小值即可
{
int mid=(l+r)/2;
if(judge(mid)==true)
{
r=mid-1;
ans=mid;
}
else
l=mid+1;
}
printf("%d\n",ans);
return 0;
}
②NOPI提高组跳石头 之前写过：here 跳石头
题意：一群组委会想要为难一只青蛙，想要把青蛙从起点跳到终点过程中的 石头移走 ，以致于导致青蛙每次跳跃的距离变大，那么请问青蛙最短跳跃距离的最大值是多少(组委会想让青蛙多跳)，但组委会 最多可以移走 m块石头
分析：首先考虑制约条件：移走的石头总数，然后我们进行二分，假设当前二分的跳跃距离是最短跳跃距离，那么青蛙在跳跃期间不可以 出现 比这个距离还短的距离，所以一旦出现我们就需要移走一块石头，最后判断一下 该距离下 移走的石头数 与 m的关系，如果移走的石头>m返回false ，缩小范围，否则扩大范围 寻找最大值。
代码之前博客中有写过，这里不再写了。
二、实数域上的二分问题
基本题型：与上述 第一种 题型类似，有一个制约条件+范围，不同的是在实数上进行二分需要注意精度问题。
①POJ2018 &&Best Cow Fences
题目大意：抽象一下，给你n个数，把这n个数分成长度最少为m的区间，问平均值最大是多少，输出平均值*1000的结果
分析：制约条件，m个区间，所以我们二分平均值，判断在该平均值下长度大于m的序列中是否有大于该平均值的，如果有则说明当前平均值还不够大，继续右移。如果没有说明平均值太小。
细节问题需要处理：
第一点：如何判断平均值是否可以分成m个区间？我们把每个数都减去当前二分的平均值，那么如果之前一段连续子序列的平均值要大于当前平均值的话 ，现在子序列的和应该大于0，所以问题转换成了 求 序列是否存在长度大于等于m的非负子段和。
第二点：对于 寻找 长度大于等于m的非负子段和的处理，首先我们记录当前所有数的前缀和，利用a1-an的和等于 sum[n]-sum[0]的方法。当n=m时，我们只能求出当前m项的和，n=m+1时，我们可以求出 1-m的和与1-m+1的和，这两个和长度均大于等于m，哪个大呢？肯定是 减去sum[0]，与sum[1]的最小值。不懂看例子
1 2 3 4 5假设找出长度不小于2的 最大的和，首先1 2是一种可能，其次1 2 3是2 3，此时比较 sum[3]-sum[1-1]与sum[3]-sum[2-1]的大小，所以说我当我们移动到某一点时，我们可以算出当前点对应的 长度大于等于m的子段的最大值，之后把所有 大于等于m的点遍历一下就好了。 (可以想象成一个区间在移动，每次都增加1，之前区间的最小值发生改变)
第三点：关于精度问题，实数上的二分通常精度卡的严，为了提高精度我们，改变区间时令 l=mid，r=mid，最大值时输出r，最小值时输出l。
代码：
bool judge(double x)
{
for(int i=1;i<=n;i++)
sum[i]=sum[i-1]+(num[i]-x);
double maxl=-INF,minl=INF;
for(int i=m;i<=n;i++)
{
minl=min(minl,sum[i-m]);
maxl=max(maxl,sum[i]-minl);
}
if(maxl>=0) return true;
return false;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%lf",&num[i]);
double l=-INF,r=INF;
double ans;
double eps=1e-5;
while(r-l>eps)
{
double mid=(l+r)/2.0;
if(judge(mid)==true) l=mid;
else r=mid;
}
printf("%d",(int)(r*1000));
return 0;
} ②Pie&&POJ3122
题目大意：有n个pie，想要分成m个人，每个人得到的pie必须来自不同的pie且体积大小相同。非常好的实数二分入门题
考虑限制条件即可：分成m个人，二分枚举当前的体积，看当前体积是否可以 从n个pie中拿到 m个pie即可。
细节问题：每人拿的都是来自不同P的，而且圆周率要到 十位 ，以后建议 只要 圆周率 的都卡到十位，不然会wa
具体代码：
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&m);m++;
double maxl=-INF;
for(int i=1;i<=n;i++)
{
scanf("%lf",&num[i]);
num[i]*=num[i];
maxl=max(num[i],maxl);
}
double l=0,r=maxl;
double eps=1e-7;//精度以后最好1e-7
while(r-l>eps)
{
double mid=(l+r)/2.0;
int cnt=0;
for(int i=1;i<=n;i++)
cnt+=(int)(num[i]/mid);
if(cnt>=m) l=mid;
else r=mid;
}
printf("%.4lf\n",r*PI);//最后*PI是为了确保精度，PI等于3.1415926至十位以上
}
return 0;
} 三、二分与其他简单问题的联系
基本题意:
题目会根据一些数学问题，即寻找中位数，寻找对数等。
此类题目有一个特征就是外要套循环，卡二分时间度，比如说寻找中位数，排序加遍历就可以找到，但是如果加一个循环T=50000，就不那么容易了。
例题 ①pair 链接好像找不到了..
基本题意：给你一些数，问你这些数中，输入n，x1，x2，xn，k，问|xb-xa|<=k的有多少对。
分析：这个题好像普通的遍历也会很麻烦，那么如何二分呢？我们首先对这组数进行排序，排序完之后就非常容易了，我们把上述 数学式化简：排序后 后面绝对比前面大 所以 直接去掉绝对值 xa-xb<=k,所以xa<=k+xb，所以我们现在只需要找到以xa为起点到第一个大于 xb+k之间有几个数，就是xa的对数，遍历一遍 序列 都找一遍，查找过程中套用二分，非常奈斯出解：
/*Accepted
Time
202ms
Memory
2172kB
Length
504
Lang
G++
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e6+5;
ll num[maxn];
ll n,m;
int main()
{
int T;scanf("%d",&T);
while(T--)
{
scanf("%lld%lld",&n,&m);
for(int i=1;i<=n;i++)
scanf("%lld",&num[i]);
sort(num+1,num+1+n);
ll cnt=0;
for(int i=1;i<=n;i++)
{
int e=upper_bound(num+i,num+1+n,num[i]+m)-num;//找到大于它的第一个位置
cnt+=e-i-1;//e-i-1即为中间的数
}
printf("%lld\n",cnt);
}
return 0;
} 时间复杂度 O(nlgn)
那么到这里，关于二分的 简单问题 的类型就说完了，二分通常用于优化复杂度，所以 也很普遍的用于复杂问题中，根源就是如何进行二分，所以说单单掌握基本题型还是不够的，还是需要善 变。
总而言之，二分的应用很广，以后有新的题型还会继续总结！加油！
京公网安备 11010502036488号