二分探索
二分探索は辞書で単語を引くのと同じです。真ん中を開き、単語がそれより前か後ろかを見て、その半分で繰り返します。整列済みリストなら、100万個の値の中からどの値でも最大20回の比較で見つかります。
考え方
整列済みのリストでは、1回の比較で、目標が見つかったかどうかだけでなく、目標がどちら側にあるかもわかります。目標を中央の値と比較します。等しければ終わりです。中央の値の方が小さければ、その前の値もすべて小さいので、目標はその後ろにしかありません。大きければ、目標はその前にしかありません。その半分だけを残して繰り返します。
例
2, 5, 8, 12, 16, 23, 38, 56, 72, 91 から23を探します。中央の値は16で、小さいので、23から91だけが残ります。その中央は56で、大きいので、23と38だけが残ります。その中央は23で、3回の比較で6番目に見つかりました。線形探索なら6回必要です。同じリストで40を探すと、16、56、23、38と比較した後に何も残りません。4回の比較で40がないとわかります。線形探索では10回です。
半分ずつならすぐ減る
1回比較すると残りは最大で半分、2回で4分の1、k回で最大およそ n/2ᵏ になります。探索は何も残らなくなると止まるので、比較は最大 ⌊log₂ n⌋ + 1 回です。40個なら6回、1,000個なら10回、100万個なら20回、10億個なら30回。リストを2倍にしても比較は1回増えるだけです。これを O(log n) と書きます。
説明は簡単、正しく書くのは難しい
John Mauchly は1946年に二分探索を説明しましたが、Donald Knuth によると、どんな長さのリストでも正しく動く最初の版が発表されたのは1962年でした。のちに Jon Bentley は、正しく書けたプロのプログラマーは10人に1人程度しかいないことを見つけました。終了条件や、半分に切るときのプラス1・マイナス1を間違えやすいのです。2006年には Joshua Bloch が、中央を求める一般的な書き方 (low + high) / 2 は非常に長いリストでオーバーフローしうることを示しました。このバグは Java のライブラリに何年も潜んでいました。このアプリのように low + (high − low) / 2 と書けば避けられます。
変種と応用
重複があると、二分探索は一致する値のどれか1つを見つけます。左または右へ探索を続ける版なら、最初や最後の一致、あるいはない値を挿入すべき位置が見つかります。同じ半分にする考え方で、方程式の根を求めたり(二分法)、バグが最初に入った版を見つけたり(git bisect)、多くの最適化パズルの答えを求めたりできます。二分探索木は、どの検索も同じように半分にしていく道筋をたどるようにデータを格納します。
試してみよう
アプリを開き、「探す値」で値を選んで「ステップ」を押します。網掛けの部分は目標がまだありうる範囲です。中央の値が強調され、除外された半分は薄くなります。タイルには、まだ候補として残っている値の数と、同じ値を線形探索で探すと何回の比較が必要かが表示されます。リストにない値を探したり、棒を40本にしたりして、差が広がる様子を見てみましょう。
よくある質問
二分探索の時間計算量は?
O(log n) です。n個の値なら比較は最大 ⌊log₂ n⌋ + 1 回。最良の場合は目標が中央にあるときで、比較1回です。反復版の追加メモリは O(1) です。
二分探索と線形探索の違いは?
線形探索は値を順に1つずつ調べ、どんなリストでも使えますが、n回の比較が必要になることがあります。二分探索は整列済みのリストでしか使えませんが、比較のたびに残りの半分を除外するので、およそ log₂ n 回で済みます。
二分探索のためだけにリストを並べ替える価値はありますか?
何度も探索する場合だけです。並べ替えにはおよそ n log n ステップかかり、1回の線形探索より多くなります。一度並べ替えれば、その後の探索はどれもとても安く済みます。
二分探索はリスト以外にも使えますか?
はい。答えのどちら側にいるかを判定できるものなら何にでも使えます。数の範囲、プログラムのバージョン、数当てゲームの推測などです。
試してみますか?
ブラウザで PictorX を開きます。インストール不要、始めるのにクレジットカードも不要です。
二分探索を試す