二分

没为啥就是想写了
模板

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;

用处:

1. 在某情况成立的情况下,其规模更大或其规模更小的情况也成立,就可以用二分法求ans
2. 与其他算法结合,并非检查的函数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;
}