2分探索（Binary Search）は、ソートされていることを前提とした配列の探索方法で、探したい値が配列の真ん中にある値より大きいか、小さいかで、探索の幅を狭めていく手法です。
線形探索（Linear Search）――配列のひとつひとつを順に見ていく――と比べると、調べる手数が少なく、効率が良くなります。
配列にあるデータ数が多くなるほど恩恵を実感することができますが、前提としてあるように、ソートされていないものには使えません。
このページでは、Pythonによる実装例と、2分探索を扱うときにサポートしてくれるライブラリ「bisect」の簡単な紹介をします。
Androidアプリを作成しました。
感情用のメモ帳です。
実装例
2分探索の具体的な流れを見ていきましょう。
以下のような小さい順にソートされた配列があり、この中から「3」があるか探します。
numbers = [1, 3, 6, 8, 12, 31, 38, 54, 73, 90]
この配列の左端のインデックス、右端のインデックス、真ん中にあるインデックスを変数に入れます。
左は「left」、右は「right」、真ん中は「middle」としました。
left = 0 right = len(numbers) - 1 middle = (left+right) // 2
whileを使いますが、条件はleftがrightより小さい間ループを回し続けます。
真ん中にある値と探したい値（今回は3）を比較し、同じか、大きいか、小さいか、で分岐させます。
同じなら処理が終了。
真ん中の値の方が大きい場合、右端のインデックスであるrightを「middle - 1」に更新。
真ん中の値の方が小さい場合、左端のインデックスであるleftを「middle + 1」に更新。
更新したものを使って「middle」を再計算して、また比較に戻ります。
# [1, 3, 6, 8, 12, 31, 38, 54, 73, 90]
while left < right:
middle = (left+right) // 2
if numbers[middle] == 3:
print(f'3が入っているのはインデックスの{middle}です')
break
elif numbers[middle] > 3:
right = middle - 1
elif numbers[middle] < 3:
left = middle + 1
ループの初回では「left 0, middle 4, right 9」で「elif numbers[middle] > 3」が真となり、rightは「middle - 1」に更新されます。
ループの2回目は「left 0, middle 1, right 3」で、配列の[1, 3, 6, 8]と範囲が狭まり、「numbers[middle] == 3」で、以下の文がprintされて処理が終了します。
3が入っているのはインデックスの1です
これまでの一連を関数にまとめます。
引数に配列と探したいものを受け取り、戻り値として、見つかった場合のインデックス（なければ-1）とループした回数を返すようにすると、次のようになりました。
import random
def binary_search(ordered_list, key):
count = 1
left = 0
right = len(ordered_list) - 1
while left < right:
middle = (left+right) // 2
if ordered_list[middle] == key:
return (middle, count)
elif ordered_list[middle] > key:
right = middle - 1
elif ordered_list[middle] < key:
left = middle + 1
count += 1
return (-1, count)
if __name__ == '__main__':
numbers = [random.randint(1, 5000) for _ in range(5000)]
numbers.sort()
key = random.randint(1, 5000)
index, count = binary_search(numbers, key)
if index == -1:
print(f'ループ回数{count}: {key}は見つかりませんでした')
else:
assert numbers[index] == key, f'{numbers[index]: {key}}'
print(f'ループ回数{count}: {key}はインデックス番号{index}です')
配列の5000個の数値、探したい数値ともにランダムで取得し、関数に渡しています。
戻り地は（インデックス番号, ループ回数）。
以下は実行結果。
$ python3 binary_search.py ループ回数8: 2029はインデックス番号1971です $ python3 binary_search.py ループ回数13: 4649は見つかりませんでした $ python3 binary_search.py ループ回数11: 438はインデックス番号434です $ python3 binary_search.py ループ回数11: 3646はインデックス番号3647です
大体10回前後のループで処理を終えています。
線形探索でやった場合、2029を探すには2000個近い数を見ていく必要があることを考えると、大分効率が良いですね。
配列のデータ数を5,000から1000倍の5,000,000に変えてみても、そこまで内部のループ回数は増えませんでした。
$ python3 binary_search.py ループ回数23: 1892329は見つかりませんでした $ python3 binary_search.py ループ回数22: 454375は見つかりませんでした $ python3 binary_search.py ループ回数22: 857302は見つかりませんでした $ python3 binary_search.py ループ回数20: 4017431はインデックス番号4017994です
数値ではなく、文字列を渡した場合でも、リストとしてアルファベット順にソートされていれば、2分探索が使えます。
さっきの関数をモジュールとして読み込み、アルファベットに対して使ってみます。
import string
from binary_search import binary_search
letters = sorted(list(string.ascii_letters))
print(letters)
index, count = binary_search(letters, 'V')
print(f'index: {index}, count: {count}')
$ python3 test.py ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z', 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z'] index: 21, count: 4
アルファベットの大文字と小文字を取得し、ソートにかけると、大文字と小文字では、小文字の方が大きく、'A'よりは'Z'の方が大きい、という扱いになります。
アルファベット「V」はletters[21]にあることがわかりました。
bisect
bisectは、ソートされたリストの状態を保ったまま挿入できるようにサポートしてくれる標準ライブラリです。
bisect --- 配列二分法アルゴリズム[docs.python.org]
2分探索をしたいときにはソート状態を保っておかなければいけませんが、値を挿入するたびに毎回ソートをかけるより効率が良くなります。
標準ライブラリのため、インストール不要。インポートすると使えます。
メソッド
主なメソッドは2つです。
リスト（list）に対象（x）を挿入したいとき、その挿入位置（インデックス）を返すメソッド。
bisect.bisect_left(list, x)
bisect.bisect_right(list, x)
leftとrightの違いは、xがすでにlistに存在した場合、既存のものの左側のインデックスを返すleft、既存のものの右側を返すrightと異なります。
リストに対象を挿入してくれるメソッド。
bisect.insort_left(list, x)
bisect.insort_left(list, x)
前のメソッドの機能＋実際の挿入まで行うメソッドです。
同じように既にlistにxが存在する場合、既存のものの左に挿入するleft、既存の右に挿入するrightと少し挙動が違います。
インポートと使用
では実際にインポートして、使ってみます。
※使用するリストは（昇順で）ソートされている必要があります。
$ python3 Python 3.10.0 (default, Oct 12 2021, 16:02:08) [GCC 9.3.0] on linux Type "help", "copyright", "credits" or "license" for more information. >>> import bisect >>> import random >>> numbers = [random.randint(0, 100) for _ in range(10)] >>> numbers [47, 30, 62, 9, 61, 46, 47, 11, 15, 8] >>> numbers.sort() >>> numbers [8, 9, 11, 15, 30, 46, 47, 47, 61, 62] >>> bisect.bisect_left(numbers, 35) 5 >>> bisect.bisect_right(numbers, 35) 5 >>> bisect.bisect_left(numbers, 9) 1 >>> bisect.bisect_right(numbers, 9) 2
bisect_leftとrightは、リストに重複するものがないときには、挙動は同じです。
重複するときには、左のインデックス、右のインデックスをそれぞれ返していますね。
挿入するにはリストのinsertメソッドにインデックスと値をそのまま渡します。
>>> numbers.insert(5, 35) >>> numbers [8, 9, 11, 15, 30, 35, 46, 47, 47, 61, 62]
挿入まで合わせてしてくれるのがinsortです。
>>> bisect.insort_left(numbers,95) >>> numbers [8, 9, 11, 15, 30, 35, 46, 47, 47, 61, 62, 95] >>> bisect.insort_right(numbers, 15) >>> numbers [8, 9, 11, 15, 15, 30, 35, 46, 47, 47, 61, 62, 95]