修了試験 2026-01-25実施分 基本情報技術者試験 問6

解説

正解は2です。 この問題は、2分探索の最大探索回数が、データ数の増加に対してどう変わるかを問うています。 2分探索は、整列済みのデータの中央の値と比べ、探索範囲を毎回半分に絞る方法です。 データ数をNとすると、最大探索回数はおよそlog2 N回です。 【計算】 データ数がNから4Nになると、最大探索回数はおよそlog2 4N回です。 log2 4N＝log2 4＋log2 N＝2＋log2 Nです。 したがって、最大探索回数は2回増えます。 【選択肢別解説】 1：× 1回増えるのは、データ数が2倍になったときです。 4倍は2の2乗なので、増えるのは2回です。 2：○ log2 4＝2なので、最大探索回数は2回増えます。 探索範囲を2回半分にすれば、4倍に増えた分を元の大きさに戻せると考えても同じ結論です。 3：× 2分探索の回数はデータ数の対数で増えるので、回数が約2倍になることはありません。 データ数が4倍になっても、増えるのは2回だけです。 4：× 約4倍になるのは、探索回数がデータ数に比例する線形探索の場合です。 2分探索では、データ数が4倍になっても2回増えるだけです。 【ポイント】 2分探索の最大探索回数は、⌊log2 N⌋＋1回と表されることもあります。 データ数が2倍になるごとに1回増えると覚えると、計算せずに判断できます。