目录
那我们今天就来说一下二分查找及二分答案
一、整数集合的二分
1.二分的基本用法
二分的基本用法就是在单调的序列或者函数中进行查找。当答案具有单调性的时候我们也可以将答进行二分，这样可以大大降低时间复杂度。通过二分，我们也可以延伸到三分等等…
2.整数二分的两个模板
我们首先要明确的是二分的前提是序列已经具有单调性，我们不能在乱序的数组上进行二分查找！！！
第一个在a这个序列中返回大于等于x最小的一个即（x或x的后继）
while (l < r)
{
int mid = l + r >> 1;
if (a[mid] >= x) r = mid;
else l = mid + 1;
}
return a[l];
第二个是在a这个序列中返回小于等于x的最大的一个即（x或x的前驱）
while(l<r)
{
int mid=(l+r+1)>>1;
if(a[mid]<=x) l=mid;
else r=mid-1;
}
return a[l];
这两个模板相当于我们在STL的函数lower_bound()和upper_bound()
3.对于两个模板的分析
我们先来看第一个模板。首先我们可以看到此时a[mid] >= x，然后我们根据a数组的单调性的话mid右边的数肯定是要比mid大，所以此时我们让右边界r=mid；然后同理我们可以得到，当a[mid] < x的时候我们就要让l = mid + 1,至于此时为什么没有让l直接等于mid，因为没有“=”号所以我们就要让l=mid+1.
同理的话我们就可以得到第二个模板是怎么来的。
4.二分的易错点分析
前提：我们在这里用到的代码结束的条件都是l=r。
首先我们可以看到我们两段代码的mid的取法是有差别的，但是为什么我们不能同时取一个呢~下面我们观察一下第二段代码，如果此时的l-r的值是1的时候，如果我们不进行加一的操作的话，按第一段代码来的话，那么此时mid=(l+r)>>1（那么此时由于向下取整的话，mid=l）；这样的话如函数递归到l=mid这一段的话，因为l本来就等于mid相当于区间并没有缩小，这样的话就会进入死循环，如果递归到r=mid-1这一段的话我们函数结束是的条件就不是l=r所以也是不正确的。
5.二分的额外拓展
我们可以发现，mid=(l+r)>>1的时候我们永远也不会取到r这个点，当mid=(l+r+1)>>1的时候我们永远也不会取到l这个点。所以此时我们可以利用这一点去处理一些无解的情况，我们可以把二分区间[1-n]扩大到[0-n]或者[1-n+1],这样的话我们如果最后二分到的点是0或者n+1的话我们就可以说明此时无解。
二、实数域上的二分
const double eps = 1e-6;
while(l-r<eps)
{
double mid=(l+r)/2;
if(check(mid)) r=mid;
else l=mid;
}
三、二分答案
当题目中有“最大值最小”或者“最小值最大”等字样的话，我们就会使用二分答案。这是判定是否使用二分最常见，最典型的特征。
二分答案的例题
算法竞赛进阶指南-最佳牛尾栏
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
double a[N],b[N],S[N];
int main()
{
int N,L;
cin>>N>>L;
for(int i=1;i<=N;i++) cin>>a[i];
double eps=1e-5;
double l=-1e6,r=1e6;
while(r-l>eps)
{
double mid=(l+r)/2;
for(int i=1;i<=N;i++) b[i] = a[i] - mid;//这里的b数组求的是减去平均值之后的数组
for(int i=1;i<=N;i++) S[i] = S[i-1] + b[i];//这里的S数组就是前缀和
double ans=-1e10;
double min_val=1e10;
for(int i=L;i<=N;i++)
{
min_val=min(min_val,S[i-L]);//min_val是最小的值，这里不用开循环找，因为每次最多只多了一个数
ans=max(ans,S[i]-min_val);
}
if(ans>=0)
l=mid;
else
r=mid;
}
cout<<(int)(r*1000)<<endl;
return 0;
}