【初心者向け】Pythonで学ぶアルゴリズム入門：二分探索の実装と応用

はじめに

More: https://www.menuvefiyat.net/

こんにちは、Qiitaで記事を書き始めたばかりのプログラマです。今日はアルゴリズム学習の最初の壁としてよく挙げられる「二分探索（バイナリサーチ）」について、Pythonでの実装方法と実際の応用例を解説したいと思います。

二分探索とは？

二分探索は、ソート済みの配列から効率的に要素を検索するアルゴリズムです。線形探索に比べて圧倒的に高速で、計算量はO(log n)となります。

基本的な考え方

1. 配列の中央の要素を調べる
2. 目的の値と中央の値を比較
3. 目的の値が中央の値より小さい場合、左半分で探索を継続
4. 目的の値が中央の値より大きい場合、右半分で探索を継続
5. 値が見つかるか、探索範囲がなくなるまで繰り返す

Pythonでの実装

def binary_search(arr, target):
    left = 0
    right = len(arr) - 1
    
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1  # 見つからなかった場合

# 使用例
sorted_list = [1, 3, 5, 7, 9, 11, 13, 15]
target = 9
result = binary_search(sorted_list, target)
print(f"要素 {target} のインデックスは {result} です")

実践的な応用例

1. ライブラリのバージョンチェック

def find_latest_compatible_version(versions, requirement):
    left, right = 0, len(versions) - 1
    result = -1
    
    while left <= right:
        mid = (left + right) // 2
        if versions[mid] >= requirement:
            result = mid
            right = mid - 1
        else:
            left = mid + 1
    return versions[result] if result != -1 else None

2. ゲーム開発での難易度調整

def find_optimal_difficulty(scores, target_score):
    left, right = 0, len(scores) - 1
    best_diff = 0
    
    while left <= right:
        mid = (left + right) // 2
        if scores[mid] >= target_score:
            best_diff = mid
            right = mid - 1
        else:
            left = mid + 1
    return best_diff

よくあるバグとデバッグ方法

1. 無限ループ: 終了条件（left <= right）を確認
2. 境界値エラー: midの計算でオーバーフローしないよう注意
3. ソートされていない配列: 事前にソートされているか確認

デバッグ時には以下のprint文を追加すると便利です：

print(f"left: {left}, right: {right}, mid: {mid}, arr[mid]: {arr[mid]}")

パフォーマンス比較

100万要素のリストから要素を検索する場合：

• 線形探索: 平均500,000回の比較
• 二分探索: 最大20回の比較

まとめ

二分探索は単純ながら強力なアルゴリズムです。実装自体はシンプルですが、応用範囲が広く、競技プログラミングや実際の開発現場でも頻繁に使用されます。ぜひマスターして、より効率的なコードを書けるようになりましょう！

次回は「二分探索の応用：平方根の計算と精度調整」について解説する予定です。お楽しみに！