BUILD YOUR UNDERSTANDING
情報処理技術者試験の用語集
言葉の意味を確かめて、問題への理解を一歩深めましょう。
二分探索
探す範囲を半分ずつ狭める
二分探索は、整列済みのデータに対して中央の値を調べ、目的の値があり得る側へ探索範囲を半分ずつ狭める方法です。大小関係を利用するため、順番がそろっていることが前提です。未整列の配列へそのまま使っても正しく探せません。比較の回数は、要素数に対して対数的に増えます。
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