アルゴリズム (全80問中60問目)
No.60
昇順に整列されたn個のデータが配列に格納されている。探索したい値を2分探索法で探索するときの，おおよその比較回数を求める式はどれか。
出典：平成18年秋期 問14
- log2n
- (log2n＋1)／2
- n
- n2
- [出題歴]
- 基本情報技術者 H21春期 問7
分類
テクノロジ系 » アルゴリズムとプログラミング » アルゴリズム
正解
ア
解説
探索アルゴリズムに関する問題は頻出です。それぞれの特徴を覚えておきましょう。
- 線形探索法
- 探索対象のデータ群の先頭から順に値を比較していく方法。データ群が整列されていなくても探索できるが、使用頻度が高い順に整列されていると少ない回数で目的のデータを探索することが可能になる。
平均比較回数:(N＋1)／2，最大比較回数:n - 2分探索法
- 探索データが昇順または降順に整列されているときに用いる方法。データ中央値と探索対象のデータを比較し、その大小により探索範囲を1／2ずつ狭めていくことで線形探索と比べて効率よく探索することが可能。
平均比較回数:[log2N]，最大比較回数:[log2N]＋1
(※[a]はaを超えない最大の整数を表します)