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