二分探索

ソート済みの 32 個から 1 つ探す方法は 2 つある。線形走査は目当ての手前を全部読む。二分探索は 1 つ読み、配列の半分を捨て、繰り返す。スライダーでターゲットを動かし、回数を比べてほしい：

注目してほしいのは、走査のコストがターゲットの位置そのものだということ —— インデックス 31に置けば比較は 32 回になる —— 一方二分探索はターゲットがどこにあっても 6 回を超えない。得をしているのは探す場所が賢いからではない。1 回の比較が「残り全体の半分」に値するからだ。

同じ探索を、配列を階段で描いたもので見る —— ソート済みとは階段のことだからだ。破線はターゲット自身の高さ。プローブはその上か下に立つだけで、判断はそれだけだ。軸上のハンドルをドラッグし、琥珀色のスライダーで比較を 1 回ずつ進めてほしい：

下のブラケットが何をしているかに注目してほしい。これはまだターゲットを持ちうるインデックスの集合で、1 つも取り落とさない：各反復の先頭で、ターゲットが配列にあるならそのインデックスは [lo, hi] の中にある。どの分岐もこれを保つ —— a[mid] < target なら mid までのインデックスはすべて小さすぎるので、lo = mid + 1 が捨てるものの中に答えになりうるものはない。

コストもこの不変条件から出てくる。長さ n の区間から mid を除くと片側に ⌊(n−1)/2⌋、もう片側に ⌈(n−1)/2⌉ が残るので、最悪の生き残りは ⌊n/2⌋ になる。n を動かして段数を数えてほしい：

最悪ケースが T(n) = 1 + T(⌊n/2⌋) に従うので、n から空までの鎖はちょうど⌊log₂ n⌋ + 1 段になる —— 32 なら 6、64 なら 7、1,024 なら 11。これは「半分になるから」ではなく数え上げの論証で、漸化式は区間が空になったところで底を打つ。1 目盛りごとに nが同じ倍率で増える軸に載せて、ハンドルを 10 億まで引いてほしい：

その軸の上では比較回数はまっすぐな階段になる ——n が倍になるたびに 1 段、100 万で 20 段、10 億で 30 段 —— その下の数字が走査が読む回数だ。空間はインデックス 3 つ —— lo、mid、hi —— n がいくつでも変わらない。

二分探索はソート済み配列を必要としない。もっと弱い条件でいい。mid で問う yes / no の問いが、真になったらそれ以降どのインデックスでも真であり続けること。ソート済みはそれを用意する最もありふれた手段にすぎない。ターゲットを動かして、配列の下の答えの帯を見てほしい：

帯が常に F…FT…T であり、F T F T にはならないことに注目してほしい —— どのターゲットでも、末尾を越えた値でもそうだ。これが本当の前提条件だ。述語が単調であること、配列の仕事はそれを成り立たせることだけ。残りは全部、帯の中の境界を見つける話だ。lower_bound、upper_bound、「通る最小の k」、「回転点」は、1 つのループと 4 つの問いにすぎない。

では前提が崩れると何が起きるか。例外ではない。下はソート済み配列で、1 本のバーだけ動かせる。探しているのは41 で、ずっとインデックス 10 にある。a[9] をそれより上まで持ち上げてほしい：

41 を越える瞬間の読み出しを見てほしい。33 より下ではすでに配列は崩れているのに、探索は正しいインデックスを返す —— このバグが本番に出るのはそれが理由で、テストデータが崩れの影響しない経路を踏んだだけなのだ。41 より上では、同じ探索が配列の中にある値に対して −1 を返し、何も報告しない。静かに失敗するので、最終的に手にするスタックトレースはまるで別の場所から来る。

だから前提条件の有用な読み方は、配列ではなく述語のほうだ。下は同じ配列を回転させたもので —— 2 つの連なりの内側以外どこもソートされていない —— それでも a[i] ≥ a[0] という問いは単調のままだ。回転量を回して最初の偽を見てほしい：

帯が T…TF…F になっていることに注目してほしい —— 前の帯の鏡像で、同じように探索できる。最初の偽が最小値のインデックスで、LC 153 と LC 33 が聞いているのはそれだ。回転ゼロ では偽がなく、ループは n を返す。前提条件は最初から配列ではない。単調だと証明できる述語を組み立てることが、難しい変種のほとんどすべてだ。

1 つ目は算術だ。lo も hi も正当なインデックスなのでそれぞれ int に収まる —— しかしその和は収まるとはかぎらない。配列長を 2³⁰ より先へドラッグして、バーが線を越えるのを見てほしい：

越えた先の (lo + hi) / 2 を見てほしい。32 ビット 2 の補数では和が桁あふれして負になり、シフトしても負のままだ —— 2³¹ − 1 要素 では中点が −3 として返ってくる。lo + (hi − lo) / 2 は、あふれようのない差から同じ中点を計算する。架空の話ではない。java.util.Arrays.binarySearch は 9 年間壊れたまま出荷され、 Bloch の 2006 年の記事が、今みんなが後者を書く理由だ。 2³⁰ 要素の int[] は 4 GiB —— 1997 年には荒唐無稽、今は普通。

2 つ目の選択は区間の流儀だ。閉区間 [lo, hi] は両端とも候補だと言い、半開区間 [lo, hi) は hi が末尾の 1 つ先だと言う。同じ「最初の真」探索を両方の流儀で進めて、2 つの hi マーカーを見てほしい：

どこに立っているかに注目してほしい。閉区間の hiは常にセルを指す。半開区間のほうはセルとセルのあいだの隙間を指し、存在しないインデックスをでっち上げずに「最後の 1 つ先」を表せる。終わり方も違う。閉区間は lo = hi + 1、半開区間は lo = hi で止まり、どちらも答えは lo にある。混ぜると while (lo <= hi) に hi = mid が組み合わさる。

それが終わらないバグだ。どの分岐も生存区間を厳密に縮めなければならないが、閉区間ループでは lo・hi・プローブが同じインデックスのとき hi = mid は縮めない。安全な規則で進めてから、壊れたほうに切り替えてほしい：

4 ステップ目以降のブラケットを見てほしい。hi = mid − 1 なら区間は空になり、ループは終わる。hi = mid なら候補 1 つの上に座り込み、読み出しがそのステップ数を数える。本番ではクラッシュではなく、張り付いたコアと決して返らないリクエストで、戻り値を調べるテストでは捕まらない。同じ検査は、その鏡像 —— 生き残る分岐が lo = mid で、中点が逆向きに丸められる場合 —— も捕まえる：

mid = lo + (hi − lo) / 2 だと、hi が lo + 1 になった時点でプローブは lo に落ちる。lo = mid は lo を自分自身に代入するだけで、区間は縮まなくなる。切り上げが修正のすべてだ。各分岐で区間が厳密に小さくなることを示し、hi == lo + 1 で試すこと。

区間の流儀が決まれば、半開区間版は 6 行で、更新し忘れる ans 変数も存在しない。lo と hi 自体が答えを挟むブラケットで、2 つが出会ったとき lo が述語の真になる最初のインデックスになる。進めてから、述語を ≥ から > に切り替えてほしい：

このスイッチがループには何の変更も加えず、lo の落ち着く先には全部の変更を加えることに注目してほしい。a[i] ≥ 8 は最初の 8 で、a[i] > 8は最後の 8 の 1 つ先で止まる。この 2 つが lower_bound と upper_bound、「最後の 8」は upper_bound − 1 だ。最右探索も、閉区間版が要求する ans = mid の記帳も書かずに済む。

おかげで数えるのはタダになる。2 つの境界が等しい値の連なり全体を挟むので、その差がそのまま個数だ。探索 2 回、走査なし、連なりが配列全体でも O(log n)。ターゲットを値のあいだで動かし、それから存在しない値へ動かしてほしい：

どちらの境界も要素の位置ではなく挿入位置なので、存在しない値についても定義される —— そのときは 2 つが一致し、ブラケットは線につぶれ、個数は 0 になる。これは存在判定でもある：i = lower_bound(x); i < n && a[i] == x。完全一致は特殊ケース、境界が一般で、組み合わせが効くのも境界のほうだ。範囲の両端を動かして、個数がついてくるのを見てほしい：

下限と上限がいま答えているのは別々の問いで、個数はその差でしかない。upper_bound(hi) − lower_bound(lo)、探索 2 回、走査なし。範囲が配列全体でも同じだ。両端を 20 の先まで押すとブラケットは線につぶれ、空の範囲はエラーではなく 0 と数えられる。挿入位置はどこでも定義されるからだ。

Koko にはバナナの山が 4 つ —— 3、6、7、11 —— と、見張りが戻るまでの 8 時間がある。速さ k なら p 本の山を ⌈p/k⌉ 時間で片づける。1 時間のうちに 2 つ目の山へ移らないからだ。速さを動かして、何口に切れるか数えてほしい：

下の帯がまた F…FT…T になっていることに注目してほしい。そうなるしかない。速く食べて遅くなることはないので、ある速さが間に合えば、それより速い速さも全部間に合う。この単調性が —— ソート済み配列はここにどこにもない —— 前提条件のすべてだ。候補は 1 … max(山)、述語 1 回の評価は山を 1 周ぶんなので、全体は O(山の数 · log 最大の山) だ。

そこで同じ半開区間の「最初の真」ループを、インデックスではなく速さの上で走らせる。ブラケットはいまや答えの区間で、mid はまだ誰も試していない速さだ：

ブラケットが 4 に閉じるのを見てほしい —— プローブ 4 回、総当たりなら 11 個の候補速度を試すところだ。膨大な種類の問題がこの形をしている。最小の積載量、最小の日数、最小の除数、そして「最大値を最小化する」あらゆる問い。難所は探索ではなく、述語を見つけ単調だと示すほうだ。単調でないとき、ループはそれでも何かを返す —— 静かに、配列が崩れていたときとまったく同じように。

答えの軸は、配列にはできないことを 1 つくれる。有界でなくてよいのだ。自然な上限がないときは、述語が真に変わるまで境界を倍にし、飛び越えた区間を二分探索する。答えをドラッグして、両方の段階を数えてほしい：

倍化の行き過ぎは 2 倍未満なので、二分の段階は倍化の段階より高くつくことがない —— 答えが a なら約 2·log₂ a プローブで、どこにも上限を仮定しない。これが指数探索で、std::equal_range が前方イテレータでしていることであり、 Timsort の galloping モードが片方の連なりだけ勝ち続けるときにしていることだ。

二分探索の最初のプローブどうしは配列の半分ぶん離れているので、それぞれが自分だけの 64 バイトキャッシュラインに落ちる。走査は 1 ラインあたり int32 を 16 個、アドレス順に読むので、ハードウェアプリフェッチャがそのコストを完全に隠す。n を動かして、琥珀色のライン数を走査が流し読みするラインと比べてほしい：

探索の終盤が 1 ラインに寄る。64 バイトに int32 は 16 個入るので、最後のプローブたちはすでに L1 にあるラインへ落ちる。何回ぶんかは読み出しが数える。一定ではない —— 整列していない 15 要素の区間は 2 ラインにまたがるからだ。 1,024 個の値 では 10 プローブで 6 ライン、2²⁰ では 19 で 16 ラインだ。その大半はプリフェッチャが先読みできないミスになる —— アドレスがまだ終わっていない比較に依存しているからだ。

数字を入れてみる。走査 1 要素は 0.25 ns —— AVX2 の比較は約 3.5 GHz で 1 サイクルに数個退役する。二分探索のプローブ 1 回 は 2.5 ns、予測器が学習できないデータ依存分岐で約半分は 15 サイクル失敗するからだ。ハッシュ参照は一律 12 ns、配列を触る 2 つには 2 ns を足す。n を交差点の向こうまで動かしてほしい：

軸が 1 目盛りごとに n を同じ倍率で増やすので、二分探索のコストは倍化ごとに 1 段上がるだけ、走査は跳ね上がる。ハッシュの一律 12 ns こそが唯一の直線だ。走査は 40 要素あたりまで持ちこたえ、その先はスライダーが届くどの n でもハッシュが最安になる —— 1,024 個の値 では 12 ns、探索は 30 ns、走査は 258 ns だ。このモデルで二分探索が単独で勝つ場面はない。残りの 2 つが答えられない問いのために選ぶのだ：

配列に無い値でどうなるかを見てほしい。ハッシュは返すものを持たないが、同じ lower_bound は前者・後者・挿入位置を言い当てる —— 実際にある値 なら在否も同時に答える。順序こそ、ハッシュが捨てたものだ。

# pred(i) が成り立つ最初のインデックス。なければ n
lo, hi = 0, n                      # 半開区間 [lo, hi)
while lo < hi:
    mid = lo + (hi - lo) // 2      # 桁あふれしない
    if pred(mid):  hi = mid        # mid はまだ候補
    else:          lo = mid + 1    # mid は除外
return lo                          # == hi。n は「真がない」の意味

16 セルの上を走らせたところ。境界はあなたの手の中、上の数字はプローブ順だ。まん中で動かしてから、末尾の先と インデックス 0 まで押し込んでほしい：

両端でも答えが返る。lo は要素でなく挿入位置なので、n は「真がない」、0 は「全部そう」を意味する。空入力の特別扱いは要らない。

このループは、自分が頼っているただ 1 つのことを検査しない。帯の答えを 1 つだけ壊しても、走り続け、停止し、インデックスを返し続ける：

途中では何も壊れない。プローブはすべて範囲内、どの分岐でも区間は縮み、戻り値も正当なインデックスだ —— ただ最初の真ではないだけで、裏返す位置によっては正しいことすらある。ループの中に足せるアサーションは無い。単調性は帯全体の性質で、ループは ⌊log₂ n⌋ + 1 セルしか見ないからだ。下の 3 つが、レビューを生き延びるバグだ：

• (lo + hi) / 2 → lo + (hi − lo) / 2。 2³⁰ 要素を超えると前者は負のインデックスを返す。
• while (lo <= hi) と hi = mid。 lo == hi で空回り。閉区間は mid − 1。
• 単調でない述語。例外も範囲外もなく、答えが返るだけ。