トップ過去問一覧基本情報技術者 平成20年・秋 > 問13
問13

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

○正解
×不正解

9

10

11

12

解説

2分探索法では、その仕組み上、1回の比較で探索範囲を約半分に絞ることができます。2000個のデータを1個まで絞るためには、以下のとおり11回の比較が必要です(矢印の箇所で比較)。

2000→1000→500→250→125→63→32→16→8→4→2→1

 

注意がいるのはデータ数が奇数の場合です。例えば125個のデータは、62、63に分割されます。最大比較回数なので、多い方の63を選択しなければなりません。

無料学習システムはこちら
→間違えた問題を繰り返し学習
→分野別学習
→模擬試験モード
デモサイト
無料ユーザ登録

問題文や解説文の内容の正確性については、できるかぎりチェックをしていますが、間違いがある可能性があります。 十分ご注意の上、参考までにご利用ください。