再帰なしで二分探索（バイナリサーチ）を実装するPythonプログラム

辞書（ディクショナリ）を使わずに二分探索（バイナリサーチ）を実装したい場合は、リストの先頭と末尾のインデックスを管理しながら、中央の値を取得していくメソッドを定義する方法があります。

取得した中央の値を検索対象の値と比較し、一致すればそのインデックスを返します。最後まで見つからなかった場合は-1を返します。

なお、二分探索が正しく機能するのは、要素が昇順または降順にソートされている場合のみである点に注意が必要です。ソートされていないリストに対して実行すると、誤った結果が返される恐れがあります。

また、Pythonのリストは整数・浮動小数点数・文字列など、異なるデータ型の値を混在させて格納できるため、柔軟に活用できます。

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

サンプルコード

def binary_search(my_list, elem):
    low = 0
    high = len(my_list) - 1
    mid = 0
    while low <= high:
        mid = (high + low) // 2
        if my_list[mid] < elem:
            low = mid + 1
        elif my_list[mid] > elem:
            high = mid - 1
        else:
            return mid
    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, 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に0を、変数midに0をそれぞれ代入します。
• 変数highには「リストの長さ - 1」を代入します。
• lowの値がhigh以下である間、床除算（//）によってmidの値を算出します。
• 検索対象の値がmid番目の要素より大きい場合は、lowをmid + 1に更新し、リストの右半分を探索します。
• 逆にmid番目の要素より小さい場合は、highをmid - 1に更新し、左半分を探索します。
• 値が一致した時点で、そのインデックスを即座に返します。
• 続いて、探索対象となるリストを定義します。
• 定義したリストと検索したい値を引数として渡し、メソッドを呼び出します。
• この操作の結果は変数に格納されます。
• 変数の内容を判定し、要素が見つかったかどうかの結果をコンソールに出力します。