アルゴリズムとプログラミング
基本情報技術者試験 科目A免除 修了試験 20140126 実施分 問7
2,000 個の相異なる要素が，キーの昇順に整列された表がある。外部から入力したキーによってこの表を 2 分探索して，該当するキーの要素を取り出す。該当するキーが必ず表中にあることが分かっているとき，キーの比較回数は最大何回か。
- ア 9
- イ 10
- ウ 11
- エ 12
出典：基本情報技術者試験 科目A免除 修了試験 20140126 実施分 問7
答えと解説を見る
正解：ウ
覚える知識
2分探索法の計算量(log2 n)
2分探索の比較回数は要素数nに対し約log2 nで、2^k≧nとなる最小のkが最大比較回数の目安となる。
この問題で必要なこと
2分探索は比較ごとに候補が半分になり、最大比較回数は ceil(log2(n+1)) 程度。2,000個では2^11=2048≧2000なので11回。
ひっかけ
log2(2000)≒10.97を切り捨てて10としてしまう。
この知識の出題：本試験系 3 回・免除試験 13 回（公開問題での観測値）