概要
絶対にバグらない二分探索の実装パターンと、それがバグらない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 mid = (ng + ok) / 2;
(f(mid) ? ok : ng) = mid;
}
if (ok == t)
cout << "for all x, f(x) = false" << endl;
else
cout << ok << endl;
お気持ち
初期値のngには、絶対に$f(x)$がfalseであるような$x$を入れておきたいです。
初期値のokには、絶対に$f(x)$がtrueであるような$x$を入れておきたいです。
もしそのような$x$が自明ならば、そうすればよいです。しかし、$f(s)$や$f(t-1)$がfalseかtrueかわからない場合も多々あると思います。そのような場合は、範囲外一個隣の値を入れておけばよい、ということをこのコードは言っています。
二分探索のバグらせ方
主に4つあります。
-
whileが収束しない。もしくは、収束後にok - ng = 1にならない場合の処理でミスる。 -
f(mid)が定義範囲外 - 全ての$x$についてf(x) = falseが検知できない
- 全ての$x$についてf(x) = trueが検知できない
これはのちに杞憂であることがわかるのですが、
- s, tがマイナスでも大丈夫？？C++のintの割り算が数学的に頭がおかしいので（
n/mは、$n \ge 0$で切り下げガウス記号$[n/m]_l$, $n < 0$で切り上げガウス記号$[n/m]^u$である、という区分性のため） - s = -INF, t = INFでも大丈夫？
一つ一つ検証していきます。
whileが収束しない。最終的にok - ng = 1にならない。
注意すべきことは、whileの終わりで常にok - ng > 1が満たされてしまう可能性です。このようなことがないことを説明します。whileの中に置いて、okとngの差は2以上あります。したがって、真にng < mid < okが満たされます。ngがmidになってもokがmidになっても、while文内の終わりではok - ngは必ず1以上小さくなります。今ok - ngは有限なので、いつかは差が1以下になります。
while文に一回でも入る場合、ok - ngが$0$以下にならないことを言います。while文内の始め、差が$2$以上なのでng < mid < okです。関数 $f$ の計算結果によって、ngがmidになったとしてもokがmidになったとしても、while文最後では、ng < okが常に成り立ちます。
次に、ok - ng == 1とならない場合でも正しく動くことを説明します。そのような場合は、while文に一回も入らない場合のみです。$s \ge t$の場合、区間がそもそも存在しません。したがって$f(x) = true$となる$x$は存在しない、と出力することが自然です。このような場合ng, okは更新されないので、そのままok = tの条件が満たされて正しく動作します。
f(mid)が定義範囲外
注意すべきことは、初期値のng, okに対して、f(ng), f(ok)が定義されていないことです。下手に実装すると、mid = ng, okとなってしまい、いかにも関数 $f$ の範囲外にアクセスしそうです。
このアルゴリズムが関数fの定義域範囲にアクセスしないことを保証したいです。つまり、任意のs - 1 <= ng, ok < tについて、ng - ok > 1の条件下で、mid = (ng + ok) / 2が$[s, t)$に収まることを示したいです。これは、okとngの差が$2$以上あるので、(ok + ng) / 2は$ok$でも$ng$でもないことから明らかです。
全てのxについてf(x) = falseが検知できない
全てfalseである場合、ok = tから動きません。したがって正しく動作します。
全てのxについてf(x) = trueが検知できない
全てtrueである場合、ng = s - 1から動きません。収束時ok - ng = 1が満たされることは上で説明したので、ok = sで収束します。したがって、ok = sですが、これは全ての$x$について$f(x) = true$であるとき、$f(x) = true$となる最小の$x$は$s$なので一致します。したがって正しく動作します。
s, tがマイナスでも大丈夫？
今の議論で言語依存の性質は、int a, bがb - a > 1であるときにa < (a + b) / 2 < bであることしか使っていません。これは(a+b)の正負によらず常に満たされるので、少なくともC++では正しく動作します。また、これが保証されない言語を僕は知りません。
s = -INF, t = INFの場合は大丈夫？
$s$に絶対に満たされないもの、$t$に絶対に満たされるものを入れておけば問題ないです。
他のやつと比較
めぐる式二分探索と比べると、コーナーケースに強いです。なぜなら、探索区間が有限である場合「解が存在する値」「解が存在しない値」の存在を前提できないケースが多いからです。逆に、今回紹介したものは「もし区間が有限ならば、ng = 左端 - 1、ok = 右端 + 1を入れておけば、めぐる式二分探索が問題なく動作する」という言い方もできると思います。
（latteさんに教えてもらったやつを納得しようとしてこのブログは生えました）
まとめ
ぼくのにぶたんパターンは、さいきょうね！
追記
このブログを書いて4時間ほどで、Twitterのプロらに以下がオーバーフローしてバグる可能性があるという指摘を受けました。
int mid = (ng + ok) / 2;
abs(ng), abs(ok) < INT_MAX / 2くらい前提させてほしいです…
「絶対にバグらない」とか煽り気味に言うと、エンジニアは厳密な生き物なので、すぐこういうのに噛み付いてきますね（intはbigintだと思って読んでください）。