アルゴリズムとプログラミング
平成26年度 秋期 基本情報技術者試験 午前 問6
2 分探索に関する記述のうち，適切なものはどれか。
- ア 2 分探索するデータ列は整列されている必要がある。
- イ 2 分探索は線形探索よりも常に速く探索できる。
- ウ 2 分探索は探索をデータ列の先頭から開始する。
- エ n 個のデータの 2 分探索に要する比較回数は，n log_2 n に比例する。
出典：平成26年度 秋期 基本情報技術者試験 午前 問6
答えと解説を見る
正解：ア
覚える知識
2分探索の前提条件(整列済みデータ)
2分探索は整列済みの配列の中央要素と比較して探索範囲を半分に絞る探索法である。
この問題で必要なこと
2分探索はデータが整列済みであることが前提で、比較回数はlog2 nに比例する。
ひっかけ
エのn log n、イの「常に速い」は計算量や条件の誤解を狙う。
この知識の出題：本試験系 2 回・免除試験 4 回（公開問題での観測値）