問題プレビューID: 174d95b8基本情報技術者試験 午前免除試験 2023年6月11日

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

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

解説

正解は「ア」です。

2 分探索法では,探索範囲の中央の値と比較し,目的の値との大小関係に応じて探索範囲を半分に絞り込みます。n 個のデータは 1 回の比較ごとに約 1/2 になるので,1 個に絞り込まれるまでの比較回数は,およそ log⁡2n\log_2 n 回となります。

  • イ: 1 回の比較で範囲が半分になるため,比較回数は log⁡2n\log_2 n 程度です。
  • ウ: 先頭から順に調べる線形探索の比較回数(平均 n/2,最悪 n)の説明です。
  • エ: 比較回数がデータ数の 2 乗になることはありません。

関連問題

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