Pythonで二分探索

ソート済み配列から目的の値を効率よく探す、二分探索（バイナリサーチ）の実装例です。コピペで動くコードと実行結果、処理の流れを確認できます。 下のコードはブラウザ内でそのまま実行できます。「実行エディタで開く」を押すと、progoのオンラインPython実行環境にコードが読み込まれ、その場で動作を確認できます。

サンプルコード

arr = [1, 3, 5, 7, 9, 11, 13]
target = 9
low, high = 0, len(arr) - 1
result = -1
while low <= high:
    mid = (low + high) // 2
    if arr[mid] == target:
        result = mid
        break
    elif arr[mid] < target:
        low = mid + 1
    else:
        high = mid - 1
print("インデックス:", result)

ポイント解説

• //で整数除算し中央値を求めます。
• 対象値との大小比較で探索範囲を絞ります。
• 計算量O(log n)で高速に探索できます。