必ず受かる情報処理技術者試験

解答・解説を見る

解答：ア

2分探索法は，整列済みの配列から効率よくデータを探索するための方法である。

2分探索法は、次の手順を繰り返すことによって、検索する方法である。

1. 整列されたデータの中央の値と対象データを比較し、それより前方にあるか後方にあるかを判断する。
2. 前方にデータがある場合は、前半分のデータの中央のデータと比較し、後方にデータがある場合は、後半分のデータの中央のデータと比較する。
   

要素数がn個の場合に2分探索法を使った場合の比較回数は，次の式で求めることができる。

平均比較回数：(log₂ n)回
最大比較回数：(log₂ n)＋1回

よってアが正解である。