平成27年度 春期 基本情報技術者試験 問6

解説

正解は1です。 2分探索法は、整列済みのデータの中央の要素と比較し、探索範囲を半分ずつ絞り込む方法です。 比較回数がデータ数nに対してどのように増えるかを考えます。 【選択肢別解説】 1：○ 1回の比較で探索範囲がほぼ半分になります。 n個のデータは、約log₂n回の比較で1個まで絞り込めます。 そのため、計算量のオーダはlog nです。 2：× nのオーダになるのは、先頭から順に調べる線形探索法です。 最悪の場合、n個すべてと比較する必要があります。 3：× n²のオーダは、バブルソートや選択ソートなど単純な整列法の計算量です。 4：× n log nのオーダは、クイックソートの平均やマージソートなど高速な整列法の計算量です。 【ポイント】 例えば1,024個のデータなら、2分探索では最大でも約10回の比較で済みます。 2分探索はデータが整列済みであることが前提である点も覚えておきましょう。