二分探索の実装と応用

はじめに

二分探索は、ソートされたリストから特定の要素を効率的に見つけるためのアルゴリズムです。線形探索と比較して、二分探索は時間計算量がO(log n)であり、大規模なデータに対して非常に効率的です。この教材では、二分探索の実装方法とその応用について学びます。

二分探索の基本

二分探索は、次の手順で動作します。

1. リストの中央の要素を調べます。
2. 中央の要素が探している値と一致する場合、探索は成功です。
3. 一致しない場合、探している値が中央の要素より小さいか大きいかを判断し、探索範囲を中央で分割します。
4. このプロセスを繰り返し、対象の要素を見つけます。

サンプルコード

以下に、Pythonでの二分探索の実装を示します。

def binary_search(arr, target):
    left, right = 0, len(arr) - 1

    while left <= right:
        mid = left + (right - left) // 2

        # 中央の要素が目標値と一致する場合
        if arr[mid] == target:
            return mid
        # 目標値が中央の要素より小さい場合
        elif arr[mid] > target:
            right = mid - 1
        # 目標値が中央の要素より大きい場合
        else:
            left = mid + 1

    # 目標値が見つからなかった場合
    return -1

コードの解説

1. binary_search関数は、ソートされたリストarrと検索したい値targetを引数に取ります。
2. leftとrightは、探索範囲のインデックスを示します。初期値はリストの最初と最後のインデックスです。
3. while left <= right:という条件でループを行い、探索範囲が有効である限り続けます。
4. midは、現在の探索範囲の中央のインデックスを計算します。left + (right - left) // 2はオーバーフローを防ぐための計算方法です。
5. 中央の要素が目標値と一致する場合、インデックスを返します。
6. 目標値が中央の要素より小さい場合、rightをmid - 1に設定し、左半分を探索します。
7. 目標値が中央の要素より大きい場合、leftをmid + 1に設定し、右半分を探索します。
8. ループが終了するまでに目標値が見つからなければ、-1を返します。

実行例

次のようなデータとターゲットを使って関数を実行できます。

arr = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
target = 7
result = binary_search(arr, target)
print(result)  # 出力は 3

この例では、arrにソート済みの整数リストがあり、targetには探したい値 7 を設定しています。この場合、出力は 3 で、これは arr のインデックス 3 に 7 があることを示しています。

実行の詳細

1. 初期設定
   left と right は、それぞれ配列の左端と右端を指します。

2. 繰り返し処理
   while left <= right: の条件でループが始まり、以下のプロセスを繰り返します。

3. 中央の要素を確認
   mid で中央のインデックスを計算します。

4. 比較と範囲の絞り込み

   • arr[mid] == target なら、目標値を発見したことになり mid を返します。
   • arr[mid] > target なら、目標値が中央より左にあるため、right = mid - 1 にして範囲を縮小します。
   • arr[mid] < target なら、目標値が中央より右にあるため、left = mid + 1 にして範囲を縮小します。

5. 目標値が見つからない場合
   探索範囲がなくなるとループが終了し、-1 を返します。

二分探索の応用

二分探索は、ソートされたリスト内で特定の要素を探す以外にも応用可能です。例えば、指定された値より大きい最小の要素を見つけることなどが挙げられます。

例題: 最小の数値を求める

次のコードは、二分探索を利用して、特定の条件を満たす最小の数値を見つける方法です。

def find_min_greater_than(arr, target):
    left, right = 0, len(arr)

    while left < right:
        mid = left + (right - left) // 2

        if arr[mid] <= target:
            left = mid + 1
        else:
            right = mid

    return left if left < len(arr) else -1

コードの解説

1. find_min_greater_than関数は、ソートされたリストarrと、条件を満たす最小の値を見つけるためのtargetを引数に取ります。
2. leftは0、rightはリストの長さで初期化されます。
3. while left < right: という条件でループを行い、探索範囲が有効である限り続けます。
4. midの計算は前述の通りです。
5. 中央の要素が target 以下の場合、左側の範囲を捨てるために left を mid + 1 に設定します。
6. 中央の要素が target より大きい場合、右側の範囲を捨てるために right を mid に設定します。
7. ループが終了した時点での left が条件を満たす最小のインデックスになります。リストの範囲内ならそのインデックスを返し、範囲外なら -1 を返します。

実行例

次のようなデータとターゲットを使って関数を実行できます。

arr = [2, 4, 6, 8, 10, 12, 14, 16, 18, 20]
target = 7
result = find_min_greater_than(arr, target)
print(result)  # 出力は 3

この場合、出力は 3 であり、arr[3] の要素である 8 が、ターゲット値 7 より大きい最小の数です。

まとめ

この教材では、二分探索の基本的な実装と応用について学びました。二分探索は、ソートされたデータに対して非常に効率的な検索手法であり、さまざまな問題に応用可能です。今後は、さらに複雑なデータ構造やアルゴリズムに挑戦してみてください。