ITパスポート試験 テクノロジ系 練習問題 第83問: 整列済みのデータを2分探索で探すとき、最悪の場合でも比較の回数を10回以内に収められるデータの件数は、最大で何件か。ここで、1回の比較では、探す値と探索範囲の中

正解: 1. 1,023

2分探索は、探索範囲の中央の値と探す値を比べ、一致しなければ探索範囲を半分に絞り込む方法である。1回比べると、中央の1件を除いた残りが二つに分かれるので、比較k回で調べ切れる件数の最大は、1回なら1件、2回なら3件、3回なら7件と増え、2のk乗から1を引いた値になる。10回では2の10乗−1＝1,023件で、1,024件にすると最悪の比較回数は11回になる。1,024は2の10乗をそのまま上限とした誤り、512と1,000は比較10回以内に収まるが最大の件数ではない。

関連キーワード: 2分探索・比較・探索範囲・整列