Ptyhonで実装するシンプルな二分探索

二分探索とは、配列やリストの中から、特定の値を効率的に探すアルゴリズムのことを指します。このアルゴリズムでは、配列やリストを半分に分割し、探したい値と比較します。比較した結果、探したい値が、分割された配列やリストのどちらにあるかを判断し、さらにその部分を分割して探索を続けます。これを繰り返すことで、最終的に探したい値が見つかるか、配列やリストを完全に探索したことを示すNoneが返されます。

以下に、Pythonで二分探索を行うプログラムを記載します。このプログラムでは、整数値の配列[1, 2, 3, 4, 5, 6, 7]から、値が4のを探します。

def binary_search(numbers, value):
    # 探索する範囲の左端点のインデックス
    left = 0
    # 探索する範囲の右端点のインデックス
    right = len(numbers) - 1

    while left <= right:
        # 探索する範囲の中央のインデックスを計算する
        mid = (left + right) // 2

        # 探索する値が、中央のインデックスの値より小さい場合
        if value < numbers[mid]:
            # 探索する範囲を、中央のインデックスより左側に絞り込む
            right = mid - 1
        # 探索する値が、中央のインデックスの値より大きい場合
        elif value > numbers[mid]:
            # 探索する範囲を、中央のインデックスより右側に絞り込む
            left = mid + 1
        # 探索する値が、中央のインデックスの値と等しい場合
        else:
            # 探索した値を返す
            return numbers[mid]

    # 探索する値が見つからなかった場合は、Noneを返す
    return None

# 整数値の配列を定義する
numbers = [1, 2, 3, 4, 5, 6, 7]

# 配列から値が4の要素を探す
result = binary_search(numbers, 4)

# 探した結果を出力する
print(result)  # => 4

二分探索の実行速度は、O(log n)です。これは、配列やリストを半分に分割することで、探索する値を効率的に見つけることができるためです。

たとえば、要素数が1,000の場合、二分探索では10回の比較で値を探すことができます。一方、線形探索では、全ての要素を比較する必要があるため、最短で1回、最悪で1,000回の比較が必要になります。

再帰版

def binary_search(numbers, value, left, right):
    # 再帰の終了条件
    # 探索する範囲が存在しない場合
    if left > right:
        return None

    # 探索する範囲の中央のインデックスを計算する
    mid = (left + right) // 2

    # 探索する値が、中央のインデックスの値より小さい場合
    if value < numbers[mid]:
        # 探索する範囲を、中央のインデックスより左側に絞り込む
        return binary_search(numbers, value, left, mid - 1)
    # 探索する値が、中央のインデックスの値より大きい場合
    elif value > numbers[mid]:
        # 探索する範囲を、中央のインデックスより右側に絞り込む
        return binary_search(numbers, value, mid + 1, right)
    # 探索する値が、中央のインデックスの値と等しい場合
    else:
        # 探索した値を返す
        return numbers[mid]

# 整数値の配列を定義する
numbers = [1, 2, 3, 4, 5, 6, 7]

# 配列から値が4の要素を探す
result = binary_search(numbers, 4, 0, len(numbers) - 1)

# 探した結果を出力する
print(result)  # => 4

どちらも名著です。是非ゲットしてみてください。

問題解決力を鍛える!アルゴリズムとデータ構造 (KS情報科学専門書)

アルゴリズム図鑑 絵で見てわかる26のアルゴリズム