修了試験 2023-12-10実施分 基本情報技術者試験 問6

解説

正解は2です。 2分探索は、整列済みのデータを毎回半分に絞り込んで探す方法です。 データ数をnとすると、最大探索回数はおよそlog₂nに比例します。 【計算】 データ数nのとき、最大探索回数はおよそlog₂n回です。 データ数4nのとき、log₂(4n)＝log₂4＋log₂n回です。 log₂4＝2なので、最大探索回数はlog₂n＋2回です。 したがって2回増えます。 【選択肢別解説】 1：× 1回増えるのは、データ数が2倍になったときです。 4倍は2を2回掛けた数なので2回増えます。 2：○ 4＝2^2なので、半分に絞る回数が2回だけ増えます。 3：× 約2倍になるのは、回数がデータ数の平方根に比例する場合などです。 2分探索は対数に比例するので誤りです。 4：× 約4倍になるのは、線形探索のように回数がデータ数に比例する場合です。 2分探索には当てはまりません。 【ポイント】 2分探索ではデータ数が2倍になるごとに最大探索回数が1回増えます。 1,024件なら約10回、約100万件でも約20回で済みます。