关于二分的正确姿势

二分本来是无脑的,只是对于答案的检索有些比较麻烦而已,实际上他的本身是不难的。这里给出几个二分的版本

int solve2() {
    int l = 0, r = 100;
    while(l < r) {
        int mid=(l+r)>>1;
        if(mid) l = mid+1;
        else r = mid - 1;
    }
    return r;
}
int solve2() {
    int l = 0, r = 100;
    while(l < r) {
        int mid=(l+r)>>1;
        if(mid) l = (ans=mid)+1;
        else r = mid - 1;
    }
    return ans;
}
for (int i=1; i<=k; i++){         //k的值取决于L-R的区间大小为2的几次方
        int mid=(L+R)>>1;
        if (ok(mid)) {ans=mid; L=mid+1;}
        else R=mid-1;
}
printf ("%d",ans);

当然,这只是综合了一下,而实际上二分的版本有很多emmm。。。前两种可以说是煞费苦心,然后,很多时候第一发都是WA的。而前两个版本也有很多人写,然后在我们这个队伍里,好像只有我用3。。。。但是他们很多时候二分WA了,我将他们while改成了for结果AC了。。。很尴尬。

但需要注意的是对于第三种情况,L可能大于R,那么mid=(L+R)>>1就会有问题,必须改成mid=L+(R-L)/2。比如UVALive3177–Beijing Guards 但对于while则没有这种顾虑。

还有一些上下界的问题,有些上下界没办法无脑0,inf之类的,比如下界不对的话就会疯狂WA。比如UVALive3177–Beijing Guards

当然有些DL例外,他们不管怎么写都是AC的。。。(什么时候我也能这样啊,羡慕)

二分练习1
二分练习2
二分练习3

上一篇:外部排序


下一篇:【总结】四边形不等式