問題プレビューID: f98b2d29基本情報技術者試験 午前免除試験 2018年12月9日

問 6
基本情報技術者試験 午前免除試験 2018年12月9日

2 分探索に関する記述のうち,適切なものはどれか。

解説

正解は「ア」です。

2 分探索は,整列済みのデータ列の中央の要素と比較し,目的の値との大小関係に応じて探索範囲を半分に絞り込む手法です。したがって,対象のデータ列はあらかじめ整列されている必要があります。

  • イ: データ列が整列されていないと 2 分探索は適用できません。また,目的の値が先頭付近にある場合は線形探索の方が速いこともあるため,「常に速い」とはいえません。
  • ウ: 2 分探索はデータ列の中央から探索を開始します。
  • エ: nn 個のデータの 2 分探索に要する比較回数は,およそ log⁡2n\log_2 n に比例します。nlog⁡2nn \log_2 n ではありません(nlog⁡2nn \log_2 n は整列の計算量の目安です)。

関連問題

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