修了試験 2016-06-12実施分 基本情報技術者試験 問7

解説

正解は1です。 2分探索法は、整列済みのデータの中央と比較し、探索範囲を半分ずつに絞り込む方法です。 n個のデータは、1回の比較でおよそn/2個に絞られます。 2回目でn/4個、k回目でn/2のk乗個になります。 範囲が1個になるのは2のk乗＝nのときで、k＝log_2 nです。 したがって、およその比較回数はlog_2 n回です。 【選択肢別解説】 1：○ 範囲を半分ずつ絞るので、比較回数はおよそlog_2 n回になります。 2：× (log_2 n＋1)/2という式は2分探索の比較回数として用いられず、平均でもおよそlog_2 n回です。 3：× n回は、線形探索で最悪の場合に必要な比較回数です。 4：× nの2乗回は、単純な整列法で必要な比較回数の程度であり、探索ではありません。 【ポイント】 線形探索の平均比較回数は(n＋1)/2回、2分探索はおよそlog_2 n回です。 2分探索は、データが整列済みであることが前提です。