アルゴリズムとプログラミング
基本情報技術者試験 科目A免除 修了試験 201001 実施分 問6
あらかじめ整列された 1000 人の電話番号から，目的の電話番号を 2 分探索法を用いて探索するとき，最大およそ何回の比較が必要になるか。
答えを選ぶ
出典：基本情報技術者試験 科目A免除 修了試験 201001 実施分 問6（問題文は IPA の公開問題。解説は当サイト作成）
解説に誤りを見つけたら、解説の誤りを報告してください。
答えと解説を見る
正解：ア
覚える知識
2分探索法の計算量(log2 n)
2分探索の比較回数はデータ数nに対しておよそlog2 n回である。
この問題で必要なこと
2分探索は1回ごとに探索範囲が半分になるので、最大比較回数はおよそlog2 n。2^10=1024≧1000より約10回。
ひっかけ
線形探索の平均回数(500)や最大回数(1000)と混同させる。
この知識の出題：本試験系 3 回・免除試験 13 回（公開問題での観測値）。頻出知識ランキング147位（全1,254件中）。