修了試験 2023-06-11実施分 基本情報技術者試験 問6

解説

正解は1です。 2分探索法（バイナリサーチ）の比較回数の目安を問う問題です。 2分探索法は、整列済みの配列の中央の値と比較し、探索範囲を毎回半分に絞り込む方法です。 【選択肢別解説】 1：○ 1回比較するごとに探索範囲が1／2になるので、n個が1個になるまでの比較回数はおよそlog_2 n回です。 例えばn＝1,024ならば、約10回の比較で見つかります。 2：× (log_2 n＋1)／2は2分探索の比較回数の目安としては用いません。 平均で半分になるという考え方は、線形探索の平均比較回数n／2と混同したものです。 3：× n回は、先頭から順に調べる線形探索で最悪の場合に必要な比較回数です。 2分探索では範囲を半分ずつに絞るので、これよりはるかに少なくなります。 4：× n^2回は、単純な整列法（バブルソートなど）の比較回数のオーダです。 探索の比較回数ではありません。 【ポイント】 2分探索の計算量はO(log n)、線形探索はO(n)です。 2分探索はデータが整列済みであることが前提条件です。