Python 二分探索アルゴリズム

ソートされたリストを対数 O(log n) 時間で検索します。ステップバイステップのロジック、エッジケース、最適化など、Python でバイナリ検索を実行して理解します。

概要

二分探索は、並べ替えられたリスト内の項目を見つけるための非常に効率的なアルゴリズムです。 O(n) 時間ですべての要素を順番にスキャンする線形検索とは異なり、二分検索は検索間隔を繰り返し半分に分割することで機能します。

検索は、配列の中央の要素を調べることから始まります。ターゲット値が中央の要素と一致する場合、その位置が返されます。ターゲットが小さい場合、アルゴリズムは検索を下半分に絞り込みます。ターゲットが大きい場合は、上半分に絞り込まれます。このプロセスは、要素が見つかるかサブ配列サイズがゼロになるまで繰り返されます。

Python で二分検索を実装するには、2 つのポインター (低位と高位) を使用してアクティブな検索境界を追跡します。各ステップで検索スペースが半分に減少するため、アルゴリズムは O(log n) 時間で実行され、大規模なデータベースに最適です。

コードと実行の出力

ソートされたリスト内のターゲット要素のインデックスを返す標準の反復バイナリ検索実装。

binary_search.py

エディターで試してみる

def binary_search(arr, target):
    low = 0
    high = len(arr) - 1
    
    while low <= high:
        mid = (low + high) // 2
        guess = arr[mid]
        
        if guess == target:
            return mid
        if guess > target:
            high = mid - 1
        else:
            low = mid + 1
            
    return -1

# Sorted test dataset
data = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
target_val = 23

index = binary_search(data, target_val)
print(f"Dataset: {data}")
print(f"Target: {target_val}")
if index != -1:
    print(f"Target found at index: {index}")
else:
    print("Target not found in dataset")

端子出力

Dataset: [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
Target: 23
Target found at index: 5

段階的な実装

データベーステーブルでのクエリのインデックス作成と検索
連続した数学的範囲でのしきい値または境界値の検索
テキストフィールドのオートコンプリート機能と検索機能

よくある質問

二分検索が機能するにはリストをソートする必要がありますか?

はい、二分検索はソートされる要素に厳密に依存します。リストが並べ替えられていない場合、比較ロジックが壊れるため、最初にリストを並べ替えるか、線形検索を使用する必要があります。

再帰的バイナリ検索ではなく反復的バイナリ検索を使用する理由は何ですか?

再帰的バイナリ検索は洗練されていますが、運用環境では反復バイナリ検索が好まれることがよくあります。反復アプローチは O(1) 補助空間で実行されますが、再帰的検索は呼び出しスタックのために O(log n) 空間を必要とし、非常に大きな入力ではスタックオーバーフローの危険があります。