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

解説

正解は1です。 2分探索法は、整列済みデータの中央の値と比べ、探索範囲を毎回半分に絞り込む方法です。 n個のデータは、約log₂n回半分にすると1個になります。 【選択肢別解説】 1：○ 1回の比較で範囲が半分になるため、比較回数はおよそlog₂n回です。 たとえばn＝1024なら約10回です。 2：× (log₂n＋1)÷2は、2分探索の比較回数の式ではありません。 2分探索の平均比較回数もおよそlog₂n回です。 3：× n回は、線形探索で最悪の場合の比較回数です。 2分探索ではこれほど多くの比較は要りません。 4：× n²回は、単純な整列法（バブルソートなど）の比較回数の目安であり、探索の比較回数ではありません。 【ポイント】 比較回数の目安は、線形探索が平均n/2回、2分探索がlog₂n回です。 2分探索は、データが整列済みであることが前提です。