二分
没为啥就是想写了
模板
int l=beign,r=end;
while(l<r)/*while(r-l<eps)*/{
int mid=(l+r)>>1;
if(check(mid)){
l=mid+1;//r=mid-1;
}
else{
r=mid-1;//l=mid-1;
}
}
ans=l;
用处:
- 在某情况成立的情况下,其规模更大或其规模更小的情况也成立,就可以用二分法求ans
- 与其他算法结合,并非检查的函数check,而是e.g.:A-B problemの排序去重二分查找=。=
时间复杂度
$O(log_2n)$
应用
1.快速幂和快速乘
template<class T>
long long quick_pow(T a,T b,T c){
int res=1;//attention!
while(b){
if(b&1)res=res*a%c;
a*=a%c;
b>>=1;
}
return res;
}
template<class T>
long long quick_mul(T a,T b,T c){
int res=0;//attention!
while(b){
if(b&1)res=(res+a)%c
a=(a+a)%c;
b>>=1;
}
return res;
}