アルゴリズムとプログラミング
基本情報技術者試験 科目A免除 修了試験 20160612 実施分 問7
昇順に整列されたn個のデータが配列に格納されている。探索したい値を2分探索法で探索するときの，およその比較回数を求める式はどれか。
- ア log₂n
- イ (log₂n+1)/2
- ウ n
- エ n^2
出典：基本情報技術者試験 科目A免除 修了試験 20160612 実施分 問7
答えと解説を見る
正解：ア
覚える知識
2分探索法の計算量(log2 n)
2分探索の比較回数はO(log2 n)で、線形探索のO(n)より少ない。
この問題で必要なこと
2分探索は1回の比較で探索範囲が半分になるので、比較回数はおよそlog2 nである。
ひっかけ
線形探索の平均比較回数(n/2)やnをそのまま選ばせる。
この知識の出題：本試験系 3 回・免除試験 13 回（公開問題での観測値）