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

解説

正解は3です。 2分探索は、整列済みの表の中央の要素と比較し、探索範囲を半分ずつに絞り込む方法です。 1回比較するごとに範囲がほぼ半分になるため、最大比較回数は要素数の対数で決まります。 該当するキーが必ず表中にあるので、範囲が1個になるまで絞り込めば見つかります。 【計算】 k回の比較で探せる要素数の上限は、2^k－1個です。 2^10－1＝1,023個なので、10回では2,000個を探しきれません。 2^11－1＝2,047個なので、11回あれば2,000個を探せます。 したがって、最大比較回数は11回です。 式で書くと、最大比較回数＝［log2 N］＋1＝［log2 2,000］＋1＝10＋1＝11回です。 【選択肢別解説】 1：× 9回で探せるのは最大2^9－1＝511個です。 2,000個には足りません。 2：× 10回で探せるのは最大1,023個です。 2,000個では最悪の場合11回目の比較が必要です。 3：○ 2^11－1＝2,047個まで探せるので、2,000個の表は最大11回の比較で見つかります。 4：× 12回は必要な回数より多い値です。 12回あれば4,095個まで探せますが、2,000個では11回で足ります。 【ポイント】 2分探索の最大比較回数は［log2 N］＋1、平均比較回数はおよそ［log2 N］です。 2^10＝1,024を覚えておくと、要素数から比較回数をすばやく見積もれます。