問題プレビューID: 99cad21a基本情報技術者試験 午前免除試験 2014年1月26日

問 7
基本情報技術者試験 午前免除試験 2014年1月26日

2,000 個の相異なる要素が,キーの昇順に整列された表がある。外部から入力したキーによってこの表を 2 分探索して,該当するキーの要素を取り出す。該当するキーが必ず表中にあることが分かっているとき,キーの比較回数は最大何回か。

解説

正解は「ウ」です。

2 分探索では,1 回の比較ごとに探索範囲がほぼ半分になります。要素数 n の表で,目的のキーが必ず存在するときの最大比較回数は,⌈log⁡2(n+1)⌉\lceil \log_2(n+1) \rceil で求められます。n=2000n = 2000 のとき,

210=1024<2001≤2048=2112^{10} = 1024 < 2001 \le 2048 = 2^{11}

なので ⌈log⁡22001⌉=11\lceil \log_2 2001 \rceil = 11 回です。したがって「ウ」が正解です。

  • ア: 9 回では 29=5122^9 = 512 通りしか判別できず,2,000 個を網羅できません。
  • イ: 10 回では 210=10242^{10} = 1024 通りで,2,000 個には不足します。
  • エ: 12 回は最大値より 1 回多く,実際には 11 回で到達できます。

関連問題

本文が同じ・似ている問題を表示しています