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