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

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

平成21年度春季問題

問題7

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

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

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

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

解答：ア

＜解説＞

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

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

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

よってアが正解である。