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