問題プレビューID: 04b8dff3基本情報技術者試験 午前免除試験 2024年7月28日

問 6
基本情報技術者試験 午前免除試験 2024年7月28日

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

解説

正解は「ア」です。

2 分探索法は,整列済みのデータの中央の要素と探索値を比較し,探索範囲を半分に絞り込む操作を繰り返します。比較回数はデータ数を半分にする操作の回数,すなわち log⁡2n\log_2 n に比例します。

  • イ: log⁡2n\log_2 n を基にした式ですが,比較回数を表す式としては不適切です。
  • ウ: nn に比例するのは,先頭から順に調べる線形探索の比較回数です。
  • エ: n2n^2 に比例するのは,2 重ループをもつ整列アルゴリズムなどの計算量です。

関連問題

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