基本情報技術者試験 - 令和6年7月修了 - 問6

答え ： ア
分野 ： テクノロジ系 › 基礎理論 › アルゴリズムとプログラミング › アルゴリズム
解説 ：
「2分探索法」は，整列済みのデータに対して探索範囲を半分ずつに絞り込みながら目的の値を探す方法です。n個のデータに対して1回の比較で探索範囲がおよそ半分になるため，探索範囲が1つになるまでの比較回数はおよそlog₂nとなります。「ア」が正解です。

「イ」の式は平均計算量の考え方を中途半端に組み合わせたような式で，2分探索法の本質的な計算量を正しく表していません。

「ウ」のnは，データを先頭から順に一つずつ調べていく線形探索法の計算量に相当します。

「エ」のn²は，二重ループを伴うような処理でよく見られる計算量であり，探索アルゴリズムとしては非効率な部類に入ります。