Python | 線形探索（break を使う） vs 二分探索アルゴリズムの比較

リストや配列から特定の値を探すとき、線形探索と二分探索は代表的な方法です。ここでは break を使った線形探索と、より効率的な二分探索を並べて比較します。

1. 線形探索（break を使う）

def linear_search(data, target):
    for i, val in enumerate(data):
        if val == target:
            return i  # 見つかったら即終了（breakと同じ効果）
    return -1  # 見つからなかった

def linear_search(data, target):
    for i, val in enumerate(data):
        if val == target:
            return i  # 見つかったら即終了（breakと同じ効果）
    return -1  # 見つからなかった

• 仕組み: 先頭から順番に1つずつチェック。
• 計算量: O(n)（要素数に比例して時間がかかる）。
• メリット: ソートされていなくても使える。
• デメリット: データが大きいと遅い。

2. 二分探索（バイナリサーチ）

def binary_search(data, target):
    low, high = 0, len(data) - 1
    while low <= high:
        mid = (low + high) // 2
        if data[mid] == target:
            return mid  # 見つかったら終了
        elif data[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1  # 見つからなかった

def binary_search(data, target):
    low, high = 0, len(data) - 1
    while low <= high:
        mid = (low + high) // 2
        if data[mid] == target:
            return mid  # 見つかったら終了
        elif data[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1  # 見つからなかった

• 仕組み: ソート済みのリストを半分に分けて、真ん中と比較しながら範囲を絞る。
• 計算量: O(log n)（要素数が増えても処理時間はゆるやかに増える）。
• メリット: 大規模データでも高速。
• デメリット: データがソートされている必要がある。

3. パフォーマンス比較（イメージ）

👉 二分探索はデータが大きくなるほど圧倒的に有利。

4. まとめ

• 線形探索:
  • ソート不要
  • 小規模データや「一度きりの探索」に便利
  • break を使うと「見つかったら即終了」で効率化できる
• 二分探索:
  • ソート済みデータが前提
  • 大規模データで非常に高速
  • アルゴリズム設計の基本中の基本

💡 実務では「データがソート済みかどうか」で使い分けます。ログ解析や入力チェックなら線形探索で十分ですが、検索エンジンやデータベースのような大規模処理では二分探索が必須です。