基本情報技術者平成20年秋期 午前問13

午前問13

2,000個の相異なる要素が,キーの昇順に整列された表がある。外部から入力したキーによってこの表を2分探索して,該当するキーの要素を取り出す。該当するキーが必ず表中にあることが分かっているとき,キーの比較回数は最大何回か。

分類

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

正解

解説

2分探索法は、要素が昇順または降順に整列された集合に対して、探索範囲を1/2に狭めることを繰り返して目的のデータを探索するアルゴリズムです。
2分探索法では目的とする値が与えられると、まず探索範囲の中央に位置する値と目的値を比較します。そして目的値の方が小さければ中央から探索範囲の最後までを、目的値の方が大きければ探索範囲の最初から中央まで探索範囲から除外して、探索範囲を1/2にします。そして再度、新たな探索範囲の中央値と目的値を比較して探索範囲を半分にする、というように同じ操作を再帰的に繰り返します。
13.gif/image-size:300×64
文字Nを探索対象全体の要素数とすると、2分探索法の平均比較回数は [log2N] 回、最大比較回数は[log2N]+1 回です(※[a]はaを超えない最大の整数を表しています)。

この設問では探索範囲の要素数が2000個(N=2000)なので、最大比較回数は[log22000]+1です。logaXは、X=apの関係のうちp(累乗指数)を表しているので、log22000を求めるには2000が2の何乗であるかを明らかにすればよいことになります。2の累乗を考えてみると、210=1024、211=2048なので、[log22000]は10になります。よって最大比較回数は10に1を加えた11回です。
© 2010-2021 基本情報技術者試験ドットコム All Rights Reserved.

Pagetop