Pythonでの二分探索アルゴリズムの実装

二分探索は、与えられたソート済み配列から特定の値を探索するアルゴリズムです。Pythonでは、リスト内の値を探索する場合に二分探索を使用することができます。ここでは、Pythonで二分探索を実装する方法について説明します。

二分探索アルゴリズムとは

二分探索は、昇順または降順にソートされた配列やリストに対して、特定の値を効率的に検索するアルゴリズムです。

二分探索は、配列やリストの中央にある要素を選択し、探している値と比較します。探している値が中央の要素よりも大きければ、中央の右側にある要素に対して同じ手順を繰り返します。探している値が中央の要素よりも小さければ、中央の左側にある要素に対して同じ手順を繰り返します。これを繰り返して、探している値が見つかるか、検索範囲がなくなるまで続けます。

二分探索のアルゴリズムの時間計算量はO(log n)であり、非常に高速です。ただし、配列やリストがソートされている必要があるため、事前にソートする必要があります。また、配列やリストの要素が更新された場合、再度ソートする必要があるため、実装には注意が必要です。

bisectモジュールを使用する方法

Pythonには、bisectというモジュールがあります。このモジュールには、二分探索を行うための関数が用意されています。以下のコードは、bisectモジュールを使用して、リスト内の値を探索する例です。

import bisect

def binary_search(arr, x):
    i = bisect.bisect_left(arr, x)
    if i != len(arr) and arr[i] == x:
        return i
    else:
        return -1

arr = [1, 2, 3, 4, 5, 6, 7, 8, 9]
x = 5
print(binary_search(arr, x))  # Output: 4

bisect_left関数は、リスト内のxより小さい値が何個あるかを返します。つまり、xが存在すれば、xのインデックスを返します。存在しない場合は、-1を返します。

自前の関数を使用する方法

自前の関数を使用して、二分探索を実装することもできます。以下のコードは、二分探索を実装するための自前の関数です。

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

arr = [1, 2, 3, 4, 5, 6, 7, 8, 9]
x = 5
print(binary_search(arr, 0, len(arr)-1, x))  # Output: 4

この関数は、再帰を使用して配列を分割し、値を探索します。midは、配列の中央のインデックスを表します。xがmidにある場合、midが返されます。xがmidより小さい場合、配列の左側を探索します。xがmidより大きい場合、配列の右側を探索します。

以下は、実際に上記の関数を使用して、配列内で値を検索する例です。

array = [1, 3, 5, 7, 9, 11]
target = 7

print(binary_search(array, target)) # 3

上記の例では、配列[1, 3, 5, 7, 9, 11]内で値7を探しています。binary_search()関数を使用して、配列内の7のインデックスを検索し、結果として3を返します。

また、配列内に指定された値が存在しない場合、上記の実装は-1を返します。たとえば、次のようにコードを書くことができます。

array = [1, 3, 5, 7, 9, 11]
target = 4

print(binary_search(array, target)) # -1

まとめ

以上がPythonで二分探索を実装する方法です。bisectモジュールを使用する方法は、短くて簡単ですが、自前の関数を使用する方法の方が理解しやすく、カスタマイズしやすいという利点があります。自前の関数を使用する場合は、再帰を使用するため、大きな配列を処理する場合には、スタックオーバーフローが発生する可能性があります。一方、bisectモジュールを使用する場合、高速に処理できるため、大きな配列を処理する場合でも問題ありません。

また、注意すべき点として、二分探索を使用する場合、必ずしも最適解が得られるわけではありません。例えば、配列内に重複した要素がある場合、どの要素を返すかが不明瞭になることがあります。このような場合は、線形探索を使用する必要があります。一方、ソートされた配列を扱う場合などは、二分探索を使用することで、O(log n)の時間複雑度で値を検索できるため、高速で効率的です。

これらのプログラムはPythonの基本的な文法とライブラリで実装することができます。Pythonの基礎学習には下記のようなサイトの利用が有効です。

click.linksynergy.com