再帰を用いた二分探索をPythonで実装する方法

再帰（リカーシブ）処理を利用して二分探索を実装する場合、まずインデックス「high」が「low」以上であるかどうかを判定するメソッドを定義します。その後、中央位置を示す「mid」変数に格納された値と検索対象の要素を比較し、その結果に応じて関数自身を再度呼び出すことで、目的の要素を絞り込みながら探索していきます。

なお、Pythonのリストは整数、浮動小数点数、文字列など、異なるデータ型の値をひとつのコレクションにまとめて格納できる汎用的なデータ構造です。

二分探索の計算量は O(log n) と非常に効率的であり、要素数が多いソート済みリストから特定の値を高速に見つけたい場合に特に有効です。

以下に具体的な実装例を示します。

サンプルコード

def binary_search(my_list, low, high, elem):
    if high >= low:
        mid = (high + low) // 2
        if my_list[mid] == elem:
            return mid
        elif my_list[mid] > elem:
            return binary_search(my_list, low, mid - 1, elem)
        else:
            return binary_search(my_list, mid + 1, high, elem)
    else:
        return -1

my_list = [ 1, 9, 11, 21, 34, 54, 67, 90 ]
elem_to_search = 1
print("The list is")
print(my_list)

my_result = binary_search(my_list,0,len(my_list)-1,elem_to_search)

if my_result != -1:
    print("Element found at index ", str(my_result))
else:
    print("Element not found!")

実行結果

The list is
[1, 9, 11, 21, 34, 54, 67, 90]
Element found at index 0

コードの解説

• まず「binary_search」という名前の関数を定義します。
• この関数は、探索対象のリスト、下限を示す変数「low」、上限を示す変数「high」、および検索したい要素を引数として受け取ります。
• 次に、変数「mid」には「high」と「low」の中間値（平均値）が代入されます。
• 「mid」の位置にある要素が検索対象と一致した場合、そのインデックスを返して処理を終了します。
• 「mid」の位置にある要素が検索対象よりも大きい場合は、探索範囲を左半分に狭めて、異なる引数を渡しながら関数を再帰的に呼び出します。
• 逆に「mid」の位置にある要素が検索対象よりも小さい場合は、探索範囲を右半分に狭めて、同様に関数を再度呼び出します。
• この処理により、探索範囲は毎回半分ずつ縮小されていきます。
• その後、実際のリストを定義し、そのリストを引数として関数を呼び出します。
• 関数の戻り値（探索結果）は変数に格納され、条件分岐によって見つかったインデックスまたは「見つからなかった」旨のメッセージがコンソールに出力されます。

このように再帰を活用することで、ループ処理を明示的に書かなくても簡潔で読みやすい二分探索を実装できます。ただし、リストが非常に大きい場合は再帰の深さ制限に注意が必要です。Pythonではデフォルトの再帰上限があるため、必要に応じて反復処理版への書き換えも検討するとよいでしょう。