Python での二分探索

  1. 二分探索アルゴリズム
  2. 二分探索のための Python プログラム
注意

二分探索について詳しく理解したい場合は、二分探索アルゴリズムの記事を参照してください。

二分探索アルゴリズム

ここでは、n の要素を含むソートされていない配列 A[] があると仮定して、要素 X を見つけたいとします。

  • lo0 とし、hin - 1 とします。
  • lo < hi の場合、mid = lo + (hi - lo)/2 とします。
    • A[mid] == X の場合、要素が見つかったのでインデックス mid を返します。
    • A[mid] < X の場合、左半分の要素を破棄して lomid+1 とします。
    • そうでない場合、A[mid] > X の場合は、右半分の要素を破棄し、himid-1 とします。
  • 要素が見つからないので -1 を返します。

二分探索のための Python プログラム

def binary_search(arr, x, n):
    lo = 0
    hi = n - 1
    mid = 0

    while lo <= hi:
        mid = (hi + lo) // 2
        if arr[mid] < x:
            lo = mid + 1
        elif arr[mid] > x:
            hi = mid - 1
        else:
            return mid
    return -1
    
arr = [ 2, 3, 4, 1, 5 ]
x = 4
n = len(arr)
result = binary_search(arr, x ,n)

if result == -1:
    print("Element not found")
else:
    print("Element is present at index", str(result))

出力:

Element is present at index 2

関連記事 - Python Algorithm

  • Python Bisect - 二分探索