探索アルゴリズム：二分探索の O(log n) とハッシュ表の平均 O(1)

0. この記事の要点

• 線形探索は $\Theta(n)$ です。ソートという前処理を一度だけ払えば、二分探索は最悪でも $\lceil \log_2(n+1) \rceil$ 回の比較で答えます。$n = 10^9$ でも 30 回です。
• 二分探索の正しさは「探索区間の外側は答えが確定している」という不変条件で証明できます。実装の誤りの大半は、この不変条件を書き下さないまま添字をいじることから生じます。
• キーどうしの比較しか使えないモデルでは $\lceil \log_2(n+1) \rceil$ 回が下界で、二分探索は最適です。これ以上速くするにはモデルを変えるしかありません。
• ハッシュ表はキーの値から添字を計算し、比較モデルの外に出ます。最悪計算量は $\Theta(n)$ のままですが、負荷率 $\alpha = n/m$ を定数に保てば探索・挿入・削除は期待 $\Theta(1)$ 時間です。
• 「平均 $O(1)$」には性質の違う 3 つの意味（データの分布仮定、ハッシュ関数の乱択、リサイズのならし）が混在しています。実務で頼ってよいのは後ろの 2 つです。
• ハッシュ表は順序を失います。最小値・範囲検索が要るなら、ソート済み配列か平衡二分探索木を選びます。

1. 動機：探索を速くするために何を捨てるか

探索は、計算機がもっとも頻繁に実行する操作です。データベースのインデックス、コンパイラのシンボル表、ルータの経路表、言語の連想配列、いずれも中身は「キーを与えると対応する値を返す」装置です。素朴にやるなら線形探索で、$n$ 個のデータに $\Theta(n)$ 時間かかります。$n$ が 10 なら誰も困りませんが、$n = 10^9$ ではどうにもなりません。$O$ 記法がスケーラビリティを測る道具だという話は 計算量とO記法 で扱いました（定義 3.1［計算量と O 記法］）。ここではその道具で、探索を速くする 2 つの道筋を最後まで追いかけます。

第 1 の道は前処理です。あらかじめデータを並べ替えておけば、1 回の比較で候補を半分に減らせます。これが二分探索で、比較回数は $\Theta(\log n)$ になります。ただしソートには $\Theta(n \log n)$ 時間かかる（ソートアルゴリズム の 定理 4.2［ソートアルゴリズム］）ので、前処理が引き合うかは検索回数次第です。$n = 10^6$ の配列を $q$ 回検索する場面を比較回数だけで概算すると、線形探索は最悪 $q \cdot 10^6$ 回、ソートしてから二分探索する方は $10^6 \log_2 10^6 + q \log_2 10^6 \approx 2 \times 10^7 + 20 q$ 回です。損益分岐点は $q \approx 20$ で、20 回より多く検索するならソートしたほうが得だと分かります。前処理は繰り返し使ってはじめて回収できるのです。

第 2 の道はキーの値を直接使うことです。比較は「大きいか小さいか」という 1 ビットしか引き出しませんが、キーが整数やビット列なら、その中身を計算に使って格納位置を決められます。これがハッシュ法で、うまくいけば $\log n$ すら要らず、平均で定数時間になります。

歴史を少しだけ挟みます。二分探索の着想自体は古く、Knuth によれば計算機上での言及は 1946 年の Mauchly の講義にさかのぼりますが、任意の長さ $n$ に対して正しく動く版が公刊されたのは 1960 年、最初の言及から 14 年後のことでした（『The Art of Computer Programming』第 3 巻 §6.2.1 の歴史的注記）。J. Bentley は『Programming Pearls』で、時間を与えられたプロの技術者の大半が正しい二分探索を書けなかったと報告しています。極めつけは 2006 年で、Java の標準ライブラリ Arrays.binarySearch が中央位置を (low + high) / 2 で計算していたために、要素数が $2^{30}$ を超えると加算が桁あふれして添字が負になる不具合が見つかりました。20 行に満たないアルゴリズムが、広く使われた標準ライブラリの中で壊れていたのです。だからこの記事では、正しさを不変条件で証明します。

ハッシュ法のほうは、Knuth の歴史的注記（同書 §6.4）によれば 1953 年 1 月の H. P. Luhn による IBM 社内メモが最初の記述で、そこにはすでにチェイン法が現れています。

ここから先は Pro プランの内容です。

この章の続き（定義・定理・証明・例・演習）をすべて読むには Pro プランにご登録ください。無料の章は最後まで読めます。

プランを見る ログイン