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

解説

正解は2です。 2分探索の最大探索回数が、データ数の増加に対してどう変わるかを問う問題です。 2分探索は、探索範囲を1回の比較ごとに半分に絞り込む方法です。 データ数をnとすると、最大探索回数はおよそlog2 nになります。 【計算】 データ数nのとき、最大探索回数はおよそlog2 nです。 データ数が4nのとき、最大探索回数はlog2 4nです。 log2 4n＝log2 4＋log2 n＝2＋log2 nです。 したがって、最大探索回数は2回増えます。 【選択肢別解説】 1：× 1回増えるのは、データ数が2倍になったときです。 半分に絞る比較が1回増えれば、2倍のデータを扱えます。 2：○ 4倍は2の2乗なので、半分に絞る比較が2回増えれば元の範囲に戻ります。 そのため、最大探索回数は2回増えます。 3：× 2分探索の回数は、データ数の対数に比例して増えます。 データ数が4倍になっても、回数が約2倍になることはありません。 4：× 回数がデータ数に比例して約4倍になるのは、先頭から順に調べる線形探索です。 2分探索ではこのような増え方はしません。 【ポイント】 2分探索の計算量はO(log n)、線形探索はO(n)です。 データ数が2^k倍になると、2分探索の最大探索回数はk回増えます。