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

解説

正解は1です。 2分探索法の比較回数の目安を問う問題です。 2分探索法は、整列済みのデータの中央の値と比較し、探索範囲を毎回半分に絞り込む方法です。 【計算】 1回比較すると、探索範囲はn/2個になります。 k回比較すると、探索範囲はn/2^k個になります。 範囲が1個になるのは、n/2^k＝1のときです。 よって、k＝log_2 nで、比較回数はおよそlog_2 n回です。 【選択肢別解説】 1：○ 範囲を毎回半分にするので、比較回数はおよそlog_2 n回です。 2：× (log_2 n＋1)／2は2分探索法の比較回数の目安ではありません。 2分探索法の比較回数はおよそlog_2 n回です。 3：× nは、先頭から順に調べる線形探索法の最大比較回数です。 線形探索法の平均比較回数は(n＋1)／2回です。 4：× n^2は、バブルソートなど基本的な整列アルゴリズムの計算量の目安です。 探索の比較回数ではありません。 【ポイント】 2分探索法はデータが整列済みであることが前提です。 データが1,024個でも、およそ10回の比較で探索できます。