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

問題14

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

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

log2n
(log2n+1)/2
n
n2

解答・解説を見る

解答:ア

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

2分探索法は、次の手順を繰り返すことによって、検索する方法である。

  1. 整列されたデータの中央の値と対象データを比較し、それより前方にあるか後方にあるかを判断する。
  2. 前方にデータがある場合は、前半分のデータの中央のデータと比較し、後方にデータがある場合は、後半分のデータの中央のデータと比較する。

要素数がn個の場合に2分探索法を使った場合の比較回数は,次の式で求めることができる。

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

よってアが正解である。

前の問題 次の問題

Copyrithg naruha