二分探索#
二分探索（Binary Search）は、ソート済みのリストに対して、探索する範囲を半分に狭めていくことで、探索する要素を見つけるアルゴリズムです。
以下の長さ10のリストから、'd'を見つけることを例に説明します。クリックするごとに以下の項目が進みます。
0〜9の真ん中である5番目の要素（インデックス番号が4）に注目する。5番目の要素jと探したい値dを比較する。dの方が小さいので、jより右側にはdは存在しない。jの左側である0〜3の範囲で探索を行う。0〜3の真ん中であるインデックス番号1の要素に注目する。1番目の要素cと探したい値dを比較する。cの方が小さい、cより左側にはdは存在しない。cの右側である2〜3の範囲で探索を行う。2〜3の真ん中である2番目の要素に注目する。2番目の要素dと探したい値dが一致するため、dが見つかった。
二分探索の例#
これを再帰呼び出しを用いて実装すると、以下のようになります。
def binary_search(list, target, start = 0, end = None):
# どのように探索が進んでいるかを確認するためのデバッグ用の出力
# print(f"start: {start}, end: {end}, len: {len(list)}")
if end is None: # 初期値として、len(list) - 1 を設定したいが、
end = len(list) - 1 # できないため、初期値を再設定する。
if start > end:
return -1
mid = (start + end) // 2 # 中央のインデックスを求める。
if list[mid] == target:
return mid
elif list[mid] < target:
return binary_search(list, target, mid + 1, end)
else:
return binary_search(list, target, start, mid - 1)
list = ['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']
assert binary_search(list, 'd') == 3, f"{list}中のインデックス 3 の要素が 'd' であるはず。"
assert binary_search([], 1) == -1, "空のリストでは -1 が返るはず。"
assert binary_search([1], 1) == 0, "唯一の要素と一致するので、インデックス 0 が返るはず。"
assert binary_search([1], 2) == -1, "唯一の要素より大きい値は見つからず、-1 が返るはず。"
assert binary_search([1, 3, 5], 0) == -1, "最小値より小さい値は見つからず、-1 が返るはず。"
assert binary_search([1, 3, 5], 4) == -1, "要素間にある存在しない値は見つからず、-1 が返るはず。"
assert binary_search([1, 3, 5], 6) == -1, "最大値より大きい値は見つからず、-1 が返るはず。"
print(binary_search(list, 'd')) # 3binary_search 関数は、リスト list から target を探索する関数です。
start と end は探索範囲に含む先頭と末尾のインデックスです。
start の初期値は 0 です。end が省略されたときだけ、None を len(list) - 1 に置き換えます。
再帰呼び出しで end が -1 になった場合は初期化せず、start > end により探索を終了します。
startとendから中央のインデックス mid を求め、list[mid] と target を比較します。
一致すれば見つかったとして、そのインデックスを返します。
一致しない場合は、list[mid] が target より小さい場合は、mid + 1 から end の範囲で再帰呼び出しを行います。
list[mid] が target より大きい場合は、start から mid - 1 の範囲で再帰呼び出しを行います。
最終的に start が end を超えた場合は、-1 を返し（2つ目のif文）、見つからなかったことを表します。