問題プレビューID: 649af651基本情報技術者試験 午前免除試験 2012年6月24日

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

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

解説

正解は「ア」です。

2 分探索法では、探索範囲の中央の値と目的の値を比較し、目的の値が中央より大きければ後半、小さければ前半に探索範囲を絞り込みます。この操作を 1 回行うごとに探索範囲はおよそ半分になるため、n 個のデータから目的の値を見つけるまでの比較回数は、n を 2 で割り続けて 1 になるまでの回数、すなわちおよそ log⁡2n\log_2 n 回となります。

  • イ: 比較回数の平均を表す式ではなく、log⁡2n\log_2 n の半分程度にはなりません。
  • ウ: nn は線形探索(先頭から順に探す方法)の比較回数に相当します。
  • エ: n2n^2 は 2 分探索の比較回数としては大きすぎます。

関連問題

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