問題プレビューID: 0735c3ef基本情報技術者試験 午前免除試験 2016年6月12日

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

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

解説

正解は「ア」です。

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

  • ウ: nn は線形探索(先頭から順に比較する方式)の比較回数です。
  • エ: n2n^2 は,例えばバブルソートなどの比較回数に相当し,2 分探索法の比較回数ではありません。
  • イ: 係数を変えただけの式であり,2 分探索法の比較回数を表しません。

関連問題

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