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

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

 ア  9  イ  10  ウ  11  エ  12


答え ウ


解説
この問題を計算で解く場合は、比較回数はlog22000の小数以下を繰上げた値になります。
log22000=10.965…ですので、比較回数としては小数第1位で繰上げして11回(ウ)になります。
試験の本番でlog22000を計算することはできないと思いますが、
 log21024=log2210=10
 log22048=log2211=11
なので、log22000は10から11の間とわかるので、比較回数の11回(ウ)が求められます。

この問題をプログラムで処理するようにシミュレートすると、2,000個のデータ列(1〜2,000)に対し2分検索を行うとき、1回目のデータ比較は(1+2,000)÷2=1,000番目のデータと行う。次に検索する範囲は1〜999(999個)か1,001〜2,000(1,000個)になる。(比較に使った要素は検索範囲から外れる。)
2回目の比較は最悪値である1,000個のデータに対し実施し、次の検索範囲は499個か500個になる。
3回目の比較を500個のデータに対し実施し、次の検索範囲は249個か250個になる。
4回目の比較を250個のデータに対し実施し、次の検索範囲は124個か125個になる。
5回目の比較を125個のデータに対し実施し、次の検索範囲は62個か62個になる。
6回目の比較を62個のデータに対し実施し、次の検索範囲は30個か31個になる。
7回目の比較を31個のデータに対し実施し、次の検索範囲は15個か15個になる。
8回目の比較を15個のデータに対し実施し、次の検索範囲は7個か7個になる。
9回目の比較を7個のデータに対し実施し、次の検索範囲は3個か3個になる。
10回目の比較を3個のデータに対し実施し、次の検索範囲は1個か1個になる。
11回目の比較でデータ内に入力されたキーがあることが確認できる。(ウ)

[ちょっと疑問]
ここで9回目のあと残り3つの中に検索しているキーがあるときを考えます。
例えば、データ列が{1, 2, 3}で“1”を検索するとき、10回目比較を中央値の2と行い1は2よりも小さいので、求めるデータは2の左にあることが分かります。
ここで、検索範囲が1で、その中に必ず検索しているデータがあることが分かっているのに、あえて11回目の比較を行う必要があるのでしょうか?


キーワード
・2分検索

キーワードの解説
  • 2分検索(二分探索、バイナリサーチ)
    整列(ソート)されたデータ列に対する検索方法で、データ列の中央の値を見て検索したい値との大小を比較し、検索する値が中央の値の左右のどちらかにあるかを判断し、検索する範囲を狭めながら行っていく方法である。

もっと、「2分検索」について調べてみよう。

戻る 一覧へ 次へ