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

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

「イ」の式は意味のない組合せであり，「ウ」のnは全件を1件ずつ調べる線形探索の計算量に相当します。「エ」のn2はさらに大きな計算量で，2分探索よりもはるかに非効率です。