二分 复杂度:o(lgn)
(有单调性一定可以二分 二分不一定有单调性)
整数二分
1 确定一个区间,使得目标值一定在区间中
2 找一个性质 满足
1)性质具有二段性(前半段具有,后半段不具有)
2)答案是二段性的分界点
3 分析中点M 在判断条件下是否成立 如果成立 考虑答案在哪个区间
如果不成立,考虑答案在哪个区间
4 如果更新方式写R=M 不用做任何处理
如果更新方式写L=M 需要在计算M时+1
停止二分:区间内只有一个数时
第一类:ans是红色区间的右端点
将[L,R]分成[L,M-1],[M,R]
if M是红色的 说明res必然在[M,R]
else res必然在[L,M-1]
while(L<R){
int M=(L+R+1)/2;
if (M红) L=M;
else R=M-1;
}
第二类 ans是绿色区间的左端点
将[L,R]分成[L,M],[M+1,R];
if M是绿 说明ans在[L,M];
else 说明 ans早[M+1,R];
while(L<R){
int M=(L+R)/2;
if (M绿) R=M;
else L=M+1;
}
模板题
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;
int main(){
int n,q;
cin>>n>>q;
int a[n];
for(int i=0;i<n;i++) scanf("%d",&a[i]);
for(int i=0;i<q;i++){
int x;
cin>>x;
//二分x的左端点
int l=0,r=n-1;//确定区间范围
while(l<r){
int mid=l+r>>1;
if(a[mid]>=x) r=mid;
else l=mid+1;
}
if(a[r]==x){//判断数字是否存在
cout<< r <<' ';
//二分x的右端点
int r=n-1;//区间为[l,n-1] (l为上面求的左端点)
while(l<r){
int mid=l+r+1>>1;
if(a[mid]<=x) l=mid;
else r=mid-1;
}
cout<< r <<endl;
}else cout<<"-1 -1"<<endl;
}
return 0;
}
实数二分
二分停止:区间足够小 while(R-L>1e-6)
将区间划分为:[L,M][M,R];
while(r-l>1e-6){//保留几位小数 取小数加2位 eg 保留4位小数 (r-l)>1e-6
double m=(r+l)/2;
if(...) l=m;
else r=m;
}
例题代码
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
int main(){
double n;
cin>>n;
double l=-10000,r=10000;
while((r-l)>1e-8){//保留6位小数
double mid=(l+r)/2;
if(mid*mid*mid>n) r=mid;
else l=mid;
}
printf("%.6f",l);
return 0;
}
三分函数 单峰函数(斜率单调)
1对斜率二分 后一个数减前一个数
2找中间两个三等分点 ML MR
1)ML<=MR L=ML
2) ML>ML R=MR
(没听懂)
若中间有值斜率为0 则不成立