基本情報技術者 試験情報＆徹底解説 -新制度に完全対応-

2分探索法は、要素が昇順または降順に整列された集合に対して、探索範囲の中央に位置する値と探索する値を比較し、探索する値の方が小さければ目的の値は範囲の先頭から中央までに、探索する値の方が大きければ目的の値は範囲の中央から最後までに存在すると判断して、次回は探索範囲を1／2に狭めて探索することを再帰的に繰り返し目的のデータを探索するアルゴリズムで、平均比較回数は「log₂N」回、最大比較回数は「log₂N＋1」回です(Nは探索対象全体の要素数)。
log_aXは、X＝a^pの関係のうちp(累乗指数)を表しているので、最大比較回数log₂2001を求めるには、2001が2の何乗であるかを計算できればいいことになります。2の累乗を考えてみると、2¹⁰＝1024，2¹¹＝2048であるためlog₂2001は10～11の間の数値であることがわかります。

したがって2000個の要素を持つ表から1つのデータを探索するときの最大比較回数は11回です。