必ず受かる情報処理技術者試験

問題7

ポケットスタディ 基本情報午後・要点整理―即効!7つの知識 (情報処理技術者試験)

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

log2n
(log2n+1)/2
n
n2

解答・解説を見る

解答:ア

2分探索法は,整列済みの配列から効率よくデータを探索するための方法である。

2分探索法は、整列されたデータの中央の値と対象データを比較し、それより前方にあるか後方にあるかを判断する。
前方にデータがある場合は、前半分のデータの中央のデータと比較し、後方にデータがある場合は、後半分のデータの中央のデータと比較する。
この操作を繰り返すことによって、検索する方法である。
要素数がn個の場合に2分探索法を使った場合の比較回数は,次の式で求めることができる。

  平均比較回数 (log2 n)回
  最大比較回数 (log2 n)+1回

よってアが正解である。

前の問題 次の問題

Copyrithg naruha