オリジナル模擬試験2 問7

問7

2,000個の相異なる要素が,キーの昇順に整列された表がある。外部から入力したキーによってこの表を2分探索して,該当するキーの要素を取り出す。該当するキーが必ず表中にあることが分かっているとき,キーの比較回数は最大何回か。
  • [出典]
  • 基本情報技術者 H20秋期 問13

分類

テクノロジ系 » アルゴリズムとプログラミング » アルゴリズム

正解

解説

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

したがって2000個の要素を持つ表から1つのデータを探索するときの最大比較回数は11回です。
© 2010-2021 基本情報技術者試験ドットコム All Rights Reserved.

Pagetop