過去問クラブ 学ぶ、わかる、つづく。
ログイン
用語解説

二分探索

探す範囲を半分ずつ狭める

二分探索は、整列済みのデータに対して中央の値を調べ、目的の値があり得る側へ探索範囲を半分ずつ狭める方法です。大小関係を利用するため、順番がそろっていることが前提です。未整列の配列へそのまま使っても正しく探せません。比較の回数は、要素数に対して対数的に増えます。

Pythonによる例

def binary_search(values, target):
    left = 0
    right = len(values) - 1
    while left <= right:
        middle = left + (right - left) // 2
        if values[middle] == target:
            return middle
        if values[middle] < target:
            left = middle + 1
        else:
            right = middle - 1
    return -1

昇順の配列を対象とし、見つからない場合は-1を返す例です。中央を確認した後は、その位置を次の範囲から除くことで、必ず範囲を狭くしています。

境界の確認

空の配列、要素が一つ、最小値より小さい値、最大値より大きい値などを考えると、終了条件の誤りを見つけやすくなります。同じ値が複数ある場合、この例は一致する位置の一つを返すだけです。最初や最後の位置を求めたいなら、比較と範囲更新の方法を変える必要があります。

計算量と前処理

一回の探索の比較回数はO(log n)ですが、未整列のデータを事前に並べ替える費用は別です。一度だけ小さな表を探す場合は、線形探索の方が簡単なこともあります。配列の中央へ直接アクセスできることも効率に関係し、単方向連結リストでは中央へ移動する負担を無視できません。

試験での要点

探索範囲の端を含むか含まないかを統一し、中央が目的より大きいときにどちらを残すかを確認します。要素数を半分にする操作を何回繰り返せるかが、比較回数の見積りの基本です。二分探索と二分探索木は関係する考え方を持ちますが、前者は探索手順、後者はデータ構造である点も区別しましょう。

参考資料

内容確認日:2026-11-13

この言葉を含む問題を探す

この用語に関連する問題

1問

用語一覧

2件