修了試験 2024-07-28実施分 基本情報技術者試験 問6

解説

正解は1です。 2分探索法の比較回数のおよその大きさ（オーダ）を問う問題です。 2分探索法は、整列済みのデータの中央の値と比較し、探索範囲を毎回半分に絞り込みます。 【選択肢別解説】 1：○ およその比較回数として適切な式です。 n個のデータを半分にする操作をk回繰り返すと範囲は1個になるので、2のk乗＝n より k＝log_2 n となります。 2：× (log_2 n＋1)／2は、2分探索法の比較回数を表す式ではありません。 最大比較回数がおよそ log_2 n＋1 回であり、それを2で割る根拠はありません。 3：× nは、線形探索法で最後まで探したときの最大比較回数です。 2分探索法では範囲を半分ずつ絞るので、nよりはるかに少なくなります。 4：× n^2は、バブルソートなど単純な整列法の比較回数のオーダです。 探索の比較回数ではありません。 【ポイント】 線形探索法の比較回数は平均 n／2 回、2分探索法は約 log_2 n 回です。 2分探索法はデータが整列済みであることが前提です。