はじめに
どんな問題を解決するか
100万個の要素があるリストから、ある値を先頭から1つずつ調べて探すと、100万回の比較が必要になることがあります。リストがソート済みなら、ずっと効率よく探せます。1回調べるごとに残りの半分を候補から外せるので、20回ほどの比較で済みます。
身近なたとえ
二分探索は、紙の辞書で単語を引くときのやり方そのものです。まず真ん中あたりを開き、探している単語がそのページより前にあるか後ろにあるかを見て、単語があるはずのない半分を捨てます。残った半分で同じことを繰り返すと、やがて目的の単語にたどり着きます。
low, high = 0, len(values) - 1📖 まだ探す必要のあるページmiddle = (low + high) // 2👆 真ん中を開くlow = middle + 1➡️ 単語は後ろ:前半を捨てるhigh = middle - 1⬅️ 単語は前:後半を捨てる二分探索は、ソート済みのリストから値を探す方法です。探す値を真ん中の要素と比べ、値があるはずのない半分を捨てることを繰り返します。かかる手順は O(log n) 回です。
重要なポイント
lowとhighは、目的の値がまだあるかもしれない範囲の両端を示します。middle = (low + high) // 2はその部分の真ん中の位置を選びます。values[middle] < targetなら目的の値は右側にあるのでlow = middle + 1、そうでなければhigh = middle - 1です。while low <= high:は範囲が空になると止まり、関数は見つからなかったことを示す-1を返します。- 17を探す場合は、12、25、17の順に調べます。比較は4回ではなく3回で済みます。
どんな場面で使う?
- ID、辞書、ソート済みのログなど、大きなソート済みデータを探す。
- リストを並べ替えたまま保つために、値を挿入する位置を見つける。
- 数当てゲームのように、もっと大きいか小さいかで答えを絞り込んでいける問題。
使わなくてよいとき
- データが並べ替えられていない場合:1回探すためだけに並べ替えると、線形探索よりかえって時間がかかります。
- 小さなリストや1回だけの検索:
inや辞書のほうが簡単で、キーでの検索を何度もするなら dict や set のほうがさらに速いです。
Pythonの二分探索(binary search)のビジュアライザー
O(log n)再生またはステップを使って、比較とデータ移動を順に確認できます。
サンプルコード
def binary_search(values, target):
low, high = 0, len(values) - 1
while low <= high:
middle = (low + high) // 2
if values[middle] == target:
return middle
if values[middle] < target:
low = middle + 1
else:
high = middle - 1
return -1
print(binary_search([3, 8, 12, 17, 25, 31], 17))
実行結果
3
コードの解説
変数lowとhighは、まだ探す範囲を表しています。真ん中の要素が探す値より小さければlow = middle + 1として左半分を捨て、そうでなければ右半分を捨てます。時間計算量はO(log n)ですが、入力のリストがあらかじめ並べ替えられていることが条件です。
値を変更し、PythonをインストールせずにCodeUtilityオンラインPythonコンパイラで実行できます。
発展問題
下のヒントにしたがってコードを書き換えてみましょう。自分で変えて結果を確かめると、コードを読むだけよりずっと深く理解できます。
- 空のリスト、要素が1つだけのリスト、重複した値を含むリストで試す。
- 各ステップの後の状態を表示して、アルゴリズムの動きを観察する。
- 要素が100個、1,000個、10,000個のときの実行時間を測り、別の解き方と比べる。
よくある間違い
ループで <= ではなく < を使う
low < high だと、最後に残った位置にある値が調べられません。
while low < high:
while low <= high:
真ん中を越えて進まない
low = middle だと、同じ真ん中をいつまでも調べ続けることがあります。
low = middle
low = middle + 1
このレッスンを終えましたか?
学習済みにすると進み具合を記録できます。
チャレンジで練習する
このレッスンの内容を使って実際の問題を解きましょう。各チャレンジはブラウザで動き、すぐにテストされ、AI のレビューも受けられます。
すべてのチャレンジ