Pythonアルゴリズム

Pythonの二分探索(binary search)

このレッスンでは、二分探索を実装し、並べ替え済みのリストから値をすばやく見つけます。

  • 中級
  • 約2分で読めます
  • 実行できるサンプル 1 件

はじめに

どんな問題を解決するか

100万個の要素があるリストから、ある値を先頭から1つずつ調べて探すと、100万回の比較が必要になることがあります。リストがソート済みなら、ずっと効率よく探せます。1回調べるごとに残りの半分を候補から外せるので、20回ほどの比較で済みます。

身近なたとえ

二分探索は、紙の辞書で単語を引くときのやり方そのものです。まず真ん中あたりを開き、探している単語がそのページより前にあるか後ろにあるかを見て、単語があるはずのない半分を捨てます。残った半分で同じことを繰り返すと、やがて目的の単語にたどり着きます。

紙の辞書からコードへ
low, high = 0, len(values) - 1📖 まだ探す必要のあるページ
middle = (low + high) // 2👆 真ん中を開く
low = middle + 1➡️ 単語は後ろ:前半を捨てる
high = middle - 1⬅️ 単語は前:後半を捨てる
比較のたびに残りが半分になるので、巨大なリストでも少ない手順で済みます。
ひと言でいうと

二分探索は、ソート済みのリストから値を探す方法です。探す値を真ん中の要素と比べ、値があるはずのない半分を捨てることを繰り返します。かかる手順は O(log n) 回です。

重要なポイント

  1. low と high は、目的の値がまだあるかもしれない範囲の両端を示します。
  2. middle = (low + high) // 2 はその部分の真ん中の位置を選びます。
  3. values[middle] < target なら目的の値は右側にあるので low = middle + 1、そうでなければ high = middle - 1 です。
  4. while low <= high: は範囲が空になると止まり、関数は見つからなかったことを示す -1 を返します。
  5. 17を探す場合は、12、25、17の順に調べます。比較は4回ではなく3回で済みます。

どんな場面で使う?

  • ID、辞書、ソート済みのログなど、大きなソート済みデータを探す。
  • リストを並べ替えたまま保つために、値を挿入する位置を見つける。
  • 数当てゲームのように、もっと大きいか小さいかで答えを絞り込んでいける問題。

使わなくてよいとき

  • データが並べ替えられていない場合:1回探すためだけに並べ替えると、線形探索よりかえって時間がかかります。
  • 小さなリストや1回だけの検索:in や辞書のほうが簡単で、キーでの検索を何度もするなら dict や set のほうがさらに速いです。

Pythonの二分探索(binary search)のビジュアライザー

O(log n)

再生またはステップを使って、比較とデータ移動を順に確認できます。

サンプルコード

コードを実行 →
main.py
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. 空のリスト、要素が1つだけのリスト、重複した値を含むリストで試す。
  2. 各ステップの後の状態を表示して、アルゴリズムの動きを観察する。
  3. 要素が100個、1,000個、10,000個のときの実行時間を測り、別の解き方と比べる。
Pythonコンパイラで実行 →

よくある間違い

ループで <= ではなく < を使う

low < high だと、最後に残った位置にある値が調べられません。

問題
while low < high:
修正
while low <= high:

真ん中を越えて進まない

low = middle だと、同じ真ん中をいつまでも調べ続けることがあります。

問題
low = middle
修正
low = middle + 1

このレッスンを終えましたか?

学習済みにすると進み具合を記録できます。

チャレンジで練習する

このレッスンの内容を使って実際の問題を解きましょう。各チャレンジはブラウザで動き、すぐにテストされ、AI のレビューも受けられます。

すべてのチャレンジ