アルゴリズムとプログラミング
基本情報技術者試験 科目A免除 修了試験 20250126 実施分 問6
2 分探索において，データの個数が 4 倍になると，最大探索回数はどうなるか。ここで，データの個数は十分に多いものとする。
- ア 1 回増える。
- イ 2 回増える。
- ウ 約 2 倍になる。
- エ 約 4 倍になる。
出典：基本情報技術者試験 科目A免除 修了試験 20250126 実施分 問6
答えと解説を見る
正解：イ
覚える知識
2分探索法の計算量(log2 n)
2分探索の最大探索回数はデータ数nに対してlog2 nのオーダである。
この問題で必要なこと
2分探索の最大探索回数はlog2 nに比例し、データ数が4倍(2^2倍)になると探索回数は2回増える。
ひっかけ
線形探索の感覚で4倍になる、あるいは2倍になると考えさせる。
この知識の出題：本試験系 3 回・免除試験 13 回（公開問題での観測値）