問題プレビューID: 50e8cb4e基本情報技術者試験 午前免除試験 2010年1月

問 6
基本情報技術者試験 午前免除試験 2010年1月

あらかじめ整列された 1000 人の電話番号から,目的の電話番号を 2 分探索法を用いて探索するとき,最大およそ何回の比較が必要になるか。

解説

正解は「ア」です。

2 分探索法は,整列されたデータの中央の値と目的の値を比較し,探索範囲を半分に絞り込むことを繰り返す。データ件数を nn としたとき,最大比較回数は 1 回の比較ごとに範囲が半分になることから,⌈log⁡2n⌉\lceil \log_2 n \rceil 回程度となる。

n=1000 のとき,log⁡21000≈9.97n = 1000 \text{ のとき,} \log_2 1000 \approx 9.97

であるから,最大比較回数は約 10 回である。したがって,正解は「ア」です。

  • イ: 46 は 1000÷21000 \div 2 に近い値であり,2 分探索の比較回数ではない。
  • ウ: 500 は 1 回の比較で絞り込まれる前の半数の件数である。
  • エ: 1000 は線形探索(順次探索)の最大比較回数である。

関連問題

本文が同じ・似ている問題を表示しています