[Python] 二分探索アルゴリズムを実装する方法

Q: 二分探索はどのような場合に使うべきですか？

二分探索は、以下のような場合に使用するのが適しています。 ソートされたデータ : 二分探索は、リストや配列がソートされていることが前提です。 ソートされたデータに対して特定の要素を迅速に検索したい場合に最適です。 大規模データセット : 大きなデータセットに対して効率的に検索を行いたい場合、二分探索の \(O(\log n)\) の時間計算量が有利です。 特定の条件を満たす要素の検索 : 左側の最小値や右側の最大値を見つけるなど、特定の条件を満たす要素を探す場合にも有効です。

Q: 再帰とループのどちらが効率的ですか？

再帰とループのどちらが効率的かは、具体的な状況によりますが、以下の点を考慮することが重要です。 メモリ使用量 : 再帰は、各呼び出しごとにスタックフレームを消費するため、メモリ使用量が増加します。 特に深い再帰が発生する場合、スタックオーバーフローのリスクがあります。 一方、ループはスタックを使用しないため、メモリ効率が良いです。 可読性 : 再帰は、アルゴリズムのロジックを直感的に表現できるため、可読性が高い場合があります。 しかし、ループの方が理解しやすいと感じる人も多いです。 パフォーマンス : 一般的には、ループの方がパフォーマンスが良いとされていますが、実際の差は微小であることが多いです。 最適な選択は、プログラムの要件や開発者の好みによります。 最終的には、どちらの方法を選ぶかは、具体的な状況や要件に応じて判断することが重要です。

二分探索アルゴリズムは、ソートされたリスト内で特定の要素を効率的に見つけるための手法です。

探索範囲を半分に絞り込むことで、時間計算量は \(O(\log n)\) となります。

Pythonでの実装は、リストの中央要素を比較し、探索対象が中央より小さい場合は左側、大きい場合は右側に探索範囲を絞り込むという手順を繰り返します。

再帰的またはループを使って実装できます。

この記事でわかること

二分探索アルゴリズムの基本
Pythonでの実装方法の詳細
時間計算量と効率性の理解
応用例とバリエーションの紹介
探索手法の選択基準の考慮

目次から探す

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

二分探索アルゴリズムは、ソートされたリストから特定の要素を効率的に検索するための手法です。

このアルゴリズムは、リストの中央の要素を比較し、検索対象が中央の要素よりも小さいか大きいかによって、探索範囲を半分に絞り込むことが特徴です。

これにより、探索の時間計算量は \(O(\log n)\) となり、非常に効率的です。

二分探索は、数値の検索だけでなく、文字列やその他のデータ型にも応用可能で、特に大規模なデータセットにおいてその効果を発揮します。

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

ループを使った二分探索の実装

ループを使用した二分探索の実装は、以下のようになります。

リストがソートされていることを前提としています。

def binary_search_loop(sorted_list, target):
    left, right = 0, len(sorted_list) - 1
    
    while left <= right:
        mid = (left + right) // 2  # 中央のインデックスを計算
        
        if sorted_list[mid] == target:
            return mid  # 要素が見つかった場合
        elif sorted_list[mid] < target:
            left = mid + 1  # 右半分を探索
        else:
            right = mid - 1  # 左半分を探索
            
    return -1  # 要素が見つからなかった場合

このコードでは、sorted_listの中からtargetを探し、見つかった場合はそのインデックスを返します。

見つからなかった場合は-1を返します。

インデックス: 3

再帰を使った二分探索の実装

再帰を使用した二分探索の実装は、以下のようになります。

def binary_search_recursive(sorted_list, target, left, right):
    if left > right:
        return -1  # 要素が見つからなかった場合
    
    mid = (left + right) // 2  # 中央のインデックスを計算
    
    if sorted_list[mid] == target:
        return mid  # 要素が見つかった場合
    elif sorted_list[mid] < target:
        return binary_search_recursive(sorted_list, target, mid + 1, right)  # 右半分を探索
    else:
        return binary_search_recursive(sorted_list, target, left, mid - 1)  # 左半分を探索

この関数は、sorted_listの中からtargetを再帰的に探します。

最初の呼び出しでは、leftを0、rightをリストの長さ-1に設定します。

インデックス: 3

Python標準ライブラリを使った二分探索

Pythonの標準ライブラリbisectを使用すると、簡単に二分探索を実装できます。

import bisect
def binary_search_bisect(sorted_list, target):
    index = bisect.bisect_left(sorted_list, target)  # 挿入位置を取得
    if index < len(sorted_list) and sorted_list[index] == target:
        return index  # 要素が見つかった場合
    return -1  # 要素が見つからなかった場合

このコードでは、bisect_leftを使用してtargetの挿入位置を取得し、その位置に要素が存在するかを確認します。

インデックス: 3

実装時の注意点

ソート状態の確認: 二分探索を行う前に、リストがソートされていることを確認する必要があります。

ソートされていないリストに対して二分探索を行うと、正しい結果が得られません。

データ型の一致: 検索対象のデータ型がリスト内の要素と一致していることを確認してください。

異なるデータ型を比較すると、エラーが発生する可能性があります。

インデックスの範囲: ループや再帰の実装では、インデックスの範囲を適切に管理することが重要です。

範囲外のインデックスにアクセスすると、エラーが発生します。

二分探索の時間計算量と効率性

線形探索との比較

線形探索は、リストの最初から最後まで順番に要素を比較していく手法です。

この方法の時間計算量は \(O(n)\) であり、リストの要素数が増えると、探索にかかる時間も直線的に増加します。

一方、二分探索はリストがソートされている場合にのみ使用でき、探索範囲を半分に絞り込むため、効率的です。

以下の表は、両者の比較を示しています。

スクロールできます

探索方法	時間計算量	特徴
線形探索	\(O(n)\)	ソート不要、全要素を比較
二分探索	\(O(\log n)\)	ソート必須、範囲を半分に絞る

二分探索の時間計算量 \(O(\log n)\)

二分探索の時間計算量は \(O(\log n)\) です。

これは、リストの要素数が \(n\) の場合、探索を行うたびに探索範囲が半分になるためです。

具体的には、最初の探索で \(n\) の要素があり、次の探索で \(n/2\)、その次で \(n/4\) と続き、最終的には \(1\) になります。

このため、二分探索は非常に効率的で、大規模なデータセットに対しても迅速に動作します。

最悪ケースと平均ケースの計算量

二分探索の最悪ケースと平均ケースの計算量は同じく \(O(\log n)\) です。

最悪ケースは、探索対象がリストの最後の要素である場合や、リストに存在しない場合です。

この場合でも、探索範囲を半分に絞り込むため、計算量は変わりません。

平均ケースも同様に、リスト内の要素が均等に分布していると仮定した場合、探索にかかる時間は \(O(\log n)\) となります。

データがソートされていない場合の影響

二分探索は、リストがソートされていることが前提です。

もしデータがソートされていない場合、二分探索を行うことはできません。

ソートされていないリストに対して二分探索を実行すると、正しい結果が得られず、無限ループやエラーが発生する可能性があります。

このため、二分探索を使用する前に、リストをソートする必要があります。

ソートの時間計算量は一般的に \(O(n \log n)\) であるため、データがソートされていない場合は、二分探索の利点が薄れることがあります。

二分探索の応用例

ソートされたリスト内での要素検索

二分探索は、ソートされたリスト内で特定の要素を効率的に検索するために広く使用されます。

例えば、数値のリストが与えられた場合、特定の数値がそのリストに存在するかどうかを迅速に確認できます。

以下は、ソートされたリスト内での要素検索の例です。

sorted_list = [1, 3, 5, 7, 9, 11]
target = 5
index = binary_search_loop(sorted_list, target)  # ループを使った二分探索
print(f"インデックス: {index}")

インデックス: 2

辞書順での文字列検索

二分探索は、辞書順での文字列検索にも利用できます。

例えば、ソートされた文字列のリストから特定の単語を探す場合、二分探索を使用することで効率的に検索できます。

以下はその例です。

sorted_words = ["apple", "banana", "cherry", "date", "fig", "grape"]
target_word = "cherry"
index = binary_search_loop(sorted_words, target_word)  # ループを使った二分探索
print(f"インデックス: {index}")

インデックス: 2

数値範囲の境界を見つける

二分探索は、数値範囲の境界を見つける問題にも応用できます。

例えば、ある条件を満たす最小または最大の数値を見つける場合に使用されます。

以下は、特定の条件を満たす最小値を見つける例です。

def find_minimum(sorted_list, condition):
    left, right = 0, len(sorted_list) - 1
    result = -1
    
    while left <= right:
        mid = (left + right) // 2
        if condition(sorted_list[mid]):
            result = sorted_list[mid]
            right = mid - 1  # 左側を探索
        else:
            left = mid + 1  # 右側を探索
            
    return result

この関数は、与えられた条件を満たす最小の数値を返します。

近似解を求める問題への応用

二分探索は、近似解を求める問題にも応用されます。

例えば、特定の関数の根を求める場合や、最適化問題において解の範囲を絞り込む際に使用されます。

以下は、数値の平方根を求める例です。

def binary_search_sqrt(x):
    left, right = 0, x
    epsilon = 0.01  # 許容誤差
    
    while left <= right:
        mid = (left + right) / 2
        if abs(mid * mid - x) < epsilon:
            return mid  # 近似解を返す
        elif mid * mid < x:
            left = mid + epsilon  # 右側を探索
        else:
            right = mid - epsilon  # 左側を探索
            
    return -1  # 解が見つからなかった場合

この関数は、与えられた数値の平方根を近似的に求めます。

二分探索のバリエーション

左側の最小値を見つける二分探索

左側の最小値を見つける二分探索は、特定の条件を満たす最初の要素を見つけるために使用されます。

例えば、ソートされたリスト内で、ある値以上の最小の要素を見つける場合に適用できます。

以下はその実装例です。

def find_leftmost(sorted_list, target):
    left, right = 0, len(sorted_list) - 1
    result = -1
    
    while left <= right:
        mid = (left + right) // 2
        
        if sorted_list[mid] >= target:
            result = mid  # 条件を満たす要素を記録
            right = mid - 1  # 左側を探索
        else:
            left = mid + 1  # 右側を探索
            
    return result

この関数は、指定されたtarget以上の最小の要素のインデックスを返します。

右側の最大値を見つける二分探索

右側の最大値を見つける二分探索は、特定の条件を満たす最後の要素を見つけるために使用されます。

例えば、ソートされたリスト内で、ある値以下の最大の要素を見つける場合に適用できます。

以下はその実装例です。

def find_rightmost(sorted_list, target):
    left, right = 0, len(sorted_list) - 1
    result = -1
    
    while left <= right:
        mid = (left + right) // 2
        
        if sorted_list[mid] <= target:
            result = mid  # 条件を満たす要素を記録
            left = mid + 1  # 右側を探索
        else:
            right = mid - 1  # 左側を探索
            
    return result

この関数は、指定されたtarget以下の最大の要素のインデックスを返します。

重複要素がある場合の二分探索

重複要素がある場合の二分探索では、特定の要素がリスト内に複数回存在する場合に、最初または最後の出現位置を見つけることができます。

以下は、最初の出現位置を見つける例です。

def find_first_occurrence(sorted_list, target):
    left, right = 0, len(sorted_list) - 1
    result = -1
    
    while left <= right:
        mid = (left + right) // 2
        
        if sorted_list[mid] == target:
            result = mid  # 要素の位置を記録
            right = mid - 1  # 左側を探索
        elif sorted_list[mid] < target:
            left = mid + 1  # 右側を探索
        else:
            right = mid - 1  # 左側を探索
            
    return result

この関数は、指定されたtargetの最初の出現位置を返します。

二分探索木との違い

二分探索木(Binary Search Tree, BST)は、データ構造の一種で、各ノードが左の子ノードよりも小さく、右の子ノードよりも大きいという特性を持っています。

二分探索木は、動的なデータの挿入や削除が可能で、平均的な探索時間は \(O(\log n)\) です。

一方、二分探索アルゴリズムは、ソートされた配列やリストに対して適用される検索手法です。

二分探索は、データ構造に依存せず、単にソートされたデータに対して効率的に動作します。

スクロールできます

特徴	二分探索アルゴリズム	二分探索木(BST)
データ構造	ソートされた配列	ノードとポインタの構造
挿入・削除	不可	可能
探索時間	\(O(\log n)\)	平均 \(O(\log n)\)
データの順序	必要	自動的に保持