読者です 読者をやめる 読者になる 読者になる

競技プログラミングをするんだよ

ICPC国内予選突破を目標に一日一問題以上解いていきます。

二分探索について

実装メモ

競技プログラミングにおいて,二分探索を使う機会はたくさんあると思います.
そして二分探索の書き方には宗教,流派があって人それぞれ意見が異なるかと思います.

整数範囲での二分探索ではwhileを使うやり方とforを使うやり方の二種類があると思います.ちなみに僕はwhile派なんですがforのほうがいい気もします.問題は変数名の取り方です.これによってバグが多発します.

ここから先は閉区間での二分探索の話をします.閉区間での二分探索はギリギリOKなところ,ギリギリダメなところをそれぞれ(top,bottom),(lowerbound,upperbound),(lb,ub)と書くと思います.この書き方はどっちがOKでどっちがアウトなのかわからずバグの原因になりがちです.慣れてる強い人はそうでもないと思いますが.

これを解消するために私はcan,cannotを使います.
この書き方にも問題点があって,canとcannotのどっちが大きい値をとるかわかりません.これには解決策があって,std::absを使います.差の絶対値をとれば関係ないのでテンプレートとしてコピペしておいてもバグが少なくなります.
あとスコープで囲っておくと便利です.

    {
        LL can,cannot;
        while(abs(can-cannot)>1){
            LL mid=(can+cannot)/2;
            if(check(mid))can=mid;
            else cannot=mid;
        }
    }

実はfor文で回数決めうちでやるとabsもいらないという.回数しっかり見積もらないと事故の原因ですが.