二分探索 — アルゴリズム・計算量・コード

二分探索は、ソート済みのリストから目的の値をすばやく見つける方法です。真ん中の要素を調べ、残りの値の半分を候補から外し、これを繰り返します。リストが順序付けされていない場合、この考え方は成り立ちません。

昇順のリストでは、ルールは単純です。中央の値が目的の値より小さければ右側を探し、大きければ左側を探します。範囲は毎回およそ半分に縮むので、二分探索の計算時間は $O(\log n)$ になります。

ソート済みリストでの二分探索のしくみ

次のソート済みリストを使います。

$$[3, 7, 12, 18, 24, 31, 39, 45, 52]$$

目的の値が $31$ だとします。

最初は全体の範囲から始めます。中央の値は $24$ です。$31 > 24$ なので、$24$ の左側にある値はすべて候補から外せます。したがって、探索は次の範囲で続きます。

$$[31, 39, 45, 52]$$

次の中央の値は $39$ です。$31 < 39$ なので、$39$ の右側にある値はすべて候補から外せます。すると範囲は次のようになります。

$$[31]$$

ここで中央の値は $31$ なので、探索は終了です。大事なのは、目的の値が見つかったことだけではありません。2回の比較で、候補の範囲は $9$ 個の値から $1$ 個まで減りました。

なぜ二分探索は $O(\log n)$ なのか

比較を1回するごとに、残っている候補のおよそ半分が除かれます。1回後には約 $n/2$ 個、2回後には約 $n/4$ 個が残ります。$k$ 回後に残る大きさはおよそ

$$\frac{n}{2^k}$$

です。

この量がおよそ $1$ になれば探索は終わるので、手順の回数は

$$2^k \approx n$$

を満たします。

両辺の $\log_2$ を取ると、

$$k \approx \log_2 n$$

となります。

これが、二分探索が大きなデータでも効率よく使える理由です。線形探索では最大で $n$ 回の確認が必要になることがありますが、二分探索では範囲を半分にし続けるために必要な回数だけで済みます。

二分探索のコード例

Pythonでの標準的な反復版は次のとおりです。