絶対にバグらない二分探索の実装パターンと、それがバグらない5つの理由 - Qiita

概要 絶対にバグらない二分探索の実装パターンと、それがバグらない5つの理由を紹介します。 めぐる式二分探索と比べると、コーナーケースに強いです（具体的には「解が存在する値」「解が存在しない値」の存在を前提しないので強いです）。 二分探索とは、判定関数 $f(x): T \rightarrow bool\ (x \in [s, t))$ が広義単調増加であるときに、 $f(x) = true$ となる最小の$x$を$O(\log (t-s))$で求めるアルゴリズムです。 …が、二分探索は、$T = int$の時、必ずバグることで有名です。何をやってもバグります。 この記事では、以下のC++のコードが、任意の広義単調増加な$f$についてあらゆるコーナーケースに常に正しく動くことを納得させます。 int ng = s - 1, ok = t; while (ok - ng > 1) { int