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

当サイトは、情報処理技術者試験に合格するためのWebサイトです。
ITパスポート試験，基本情報技術者,応用情報技術者,高度試験の過去問題と解答及び詳細な解説を掲載しています。
  1. トップページ
  2. 基本情報技術者
  3. 平成18年度秋季問題一覧
  4. 平成18年度秋季問題14-解答・解説-分析

平成18年度秋季問題

問題14

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

ア log2n
イ (log2n+1)/2
ウ n
エ n2

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

ア log2n
イ (log2n+1)/2
ウ n
エ n2

解答：ア

＜解説＞

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

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

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

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

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

よってアが正解である。