問題プレビューID: b6f9033f基本情報技術者試験 午前免除試験 2014年6月22日

問 6
基本情報技術者試験 午前免除試験 2014年6月22日

昇順に整列された nn 個のデータが配列に格納されている。探索したい値を 2 分探索法で探索するときの,およその比較回数を求める式はどれか。

解説

正解は「ア」です。

2 分探索法は,整列済みのデータの中央の値と探索値を比較し,探索範囲を半分に絞り込む操作を繰り返します。1 回の比較で探索範囲がおよそ半分になるため,nn 個のデータを探索するのに必要な比較回数はおよそ log⁡2n\log_2 n 回となります。したがって「ア」が正解です。

  • イ: (log⁡2n+1)/2(\log_2 n+1)/2 は 2 分探索の比較回数ではありません。
  • ウ: nn は先頭から順に探す線形探索の比較回数(最大)です。
  • エ: n2n^2 は要素の総当たり比較などに対応する値で,2 分探索とは無関係です。

関連問題

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