二分探索

二分探索

#

二分探索（Binary Search）は，ソート済みのリストに対して，探索する範囲を半分に狭めていくことで，探索する要素を見つけるアルゴリズムです． 以下の長さ10のリストから，'d'を見つけることを例に説明します．クリックするごとに以下の項目が進みます．

• 0〜9 の真ん中である 4 番目の要素に注目する．
• 4番目の要素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 = -1):
    # どのように探索が進んでいるかを確認するためのデバッグ用の出力
    # print(f"start: {start}, end: {end}, len: {len(list)}") 
    if end == -1:           # 初期値として，len(list) を設定したいが，
        end = len(list)     # できないため，初期値を再設定する．
    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' であるはず．"

print(binary_search(list, 'd')) # 3

binary_search 関数は，リスト list から target を探索する関数です． start と end は探索範囲を指定するための引数で，初期値はそれぞれ 0 と len(list) - 1 です． startとendから中央のインデックス mid を求め，list[mid] と target を比較します． 一致すれば見つかったとして，そのインデックスを返します． 一致しない場合は，list[mid] が target より小さい場合は，mid + 1 から end の範囲で再帰呼び出しを行います． list[mid] が target より大きい場合は，start から mid - 1 の範囲で再帰呼び出しを行います． 最終的に start が end を超えた場合は，-1 を返し（2つ目のif文），見つからなかったことを表します．