平成21年春期試験問題 午前問7

午前試験免除制度対応!基本情報技術者試験のeラーニング【独習ゼミ】
昇順に整列されたn個のデータが配列に格納されている。探索したい値を2分探索法で探索するときの,およその比較回数を求める式はどれか。

  • log2n
  • (log2n+1)/2
  • n
  • n2
正解 問題へ
分野:テクノロジ系
中分類:アルゴリズムとプログラミング
小分類:アルゴリズム
解説
探索アルゴリズムに関する問題は頻出です。それぞれの特徴を覚えておきましょう。
線形探索法
探索対象のデータ群の先頭から順に値を比較していく方法。データ群が整列されていなくても探索できるが、使用頻度が高い順に整列されていると少ない回数で目的のデータを探索することが可能になる。
平均比較回数:(N+1)/2,最大比較回数:n
2分探索法
探索データが昇順または降順に整列されているときに用いる方法。データ中央値と探索対象のデータを比較し、その大小により探索範囲を1/2ずつ狭めていくことで線形探索と比べて効率よく探索することが可能。
平均比較回数:[log2N],最大比較回数:[log2N]+1
(※[a]はaを超えない最大の整数を表します)

この問題の出題歴


Pagetop