二分是我之前也没怎么好好学的一部分，这次顺带着理解了一些之前不太理解的东西
首先是二分的意思，实际上是一种对区间进行每次处理时都只取区间的一半，然后是一半的一半，一半的一半的一半....
因此对于长度为n的序列而言，一个单独二分的复杂度是logn
那么在什么情况下我们可以想到用二分呢？
我们从这个方法本身来看，既然每次都要取一半，那我们就要清楚哪一半究竟才是正确的
我们会取一个mid值，一般将[l,r]区间划分为[l,mid]和[mid+1,r]或者[l,mid-1]和[mid,r]（对于整数而言）
我们每次都要对mid处的值进行检查，以此来判断要求的答案是在左边区域还是右边区域。
也就是说，如果无法区分左边区域和右边区域哪个正确，也就无法二分
所以左边的区域必须有一种性质，右边区域有另外一种性质。这种性质一般就是是否满足某个条件。
并且由于二分到最后范围会缩小到一个数，因此序列里的所有数都可能会成为mid。每次都要对mid处值进行判定。所以对于每个序列上的数而言，都可以从左边的区域和右边的区域中选择正确的一个
像这样不论对哪个位置而言，都有一边满足条件，另一边不满足，可以把它叫做答案的单调性
当对象是单调数列时，我们很容易能想到二分。但当答案具有单调性时我们却不太容易注意到
洛谷P2249
很经典的单调序列查找，需要找到改数字第一次在序列中出现的位置
当mid处的值小于答案时，说明答案在右半部分，大于时，答案在左半部分
等于时，可能是该位置本身，也可能是左边的区域。因此划分区域时最好直接选择[l,mid]将mid自身划进去
#include<bits/stdc++.h>
using namespace std;
int n,m;
int a[1000005];
void ser(int l,int r,int ans)
{
if(l>r) return;
if(l==r)
{
if(ans!=a[r])
{
printf("-1 ");
return;
}
printf("%d ",l);
return;
}
int mid=(l+r)>>1;
if(a[mid]<ans) ser(mid+1,r,ans);
else ser(l,mid,ans);
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
for(int i=1;i<=m;i++)
{
int q;
scanf("%d",&q);
ser(1,n,q);
}
return 0;
}
洛谷P1824
这个就是答案的单调性。
要将牛插入进牛棚里，求最大的最近距离，范围是1e9
设这个最大的最近距离为F，当最近距离小于F时满足可以把牛都填进去这一条件
当最近距离大于F时，必然无法填完，因为F是最大的满足该条件的
因此在牛棚区域内进行二分，对于每个mid看看是否满足条件来判断答案在左还是在右。
判断方法为从1到n循环，从第一个开始填，很显然当一个位置减去上一个填的位置得到的结果大于设定的最近距离时便可将其填入。并且当i为1时是必填入的。循环完后查看是否将牛填完
复杂度最大为nlog1e9
#include<bits/stdc++.h>
using namespace std;
int n,c;
int a[100005];
bool cmp(int mid)//判断该最近距离是否合法
{
int last=1,sum=1;//第一个是肯定要加进去的
for(int i=2;i<=n;i++)
{
if(a[i]-a[last]>=mid) last=i,sum++;
}
if(sum>=c) return true;
else return false;//放不了c头
}
void ser(int l,int r)
{
if(l>r) return;
if(l==r)
{
printf("%d",l);
return;
}
int mid=(l+r+1)/2;
//cout<<l<<' '<<r<<endl;
if(!cmp(mid)) ser(l,mid-1);//最近距离大于F
else ser(mid,r);
return;
}
int main()
{
//求最近距离的最大值，设为F，当最近距离大于F时
//没有方案安置牛棚，当最近距离小于等于F时则一定存在至少
//一种方案
//在（1，Xn)范围内进行二分，对每个mid作为最近距离进行判定
//
scanf("%d%d",&n,&c);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
sort(a+1,a+n+1);
ser(1,a[n]);
return 0;
}
洛谷P1024
这题数据很弱，暴力枚举也能过，最后保留两位，即使枚举1e-4的精度也只有2*1e6
但目的是为了练二分....
这道题给了一个判定条件，并且每个答案相差大于1，因此可以对-100到100的200个区间分别进行二分
当区间边界已经接近答案时用判定条件将无法生效，因为代入原式直接就是0，因此直接输出后return即可
区间只用输出一个端点即可，两个端点会重复
#include<bits/stdc++.h>
using namespace std;
double a,b,c,d;
double minn=1e-4;
void search(double l,double r)
{
if(l>r) return;
if(r-l<=minn)
{
printf("%.2lf ",l);
return;
}
//printf("%.2llf %.2llf\n",l,r);
double mid=(l+r)/2;
double fx1=a*l*l*l+b*l*l+c*l+d,fx2=a*r*r*r+b*r*r+c*r+d;
double fm=a*mid*mid*mid+b*mid*mid+c*mid+d;
if(fx1==0) {printf("%.2lf ",l);return;}
if(fx2*fm<0) search(mid+minn,r);
if(fx1*fm<0) search(l,mid);
}
int main()
{
//范围是-100到100
cin>>a>>b>>c>>d;
for(int i=-100;i<=99;i++)
{
search(double(i),double(i+1));
}
return 0;
}