基本情報技術者 試験情報＆徹底解説 -新制度に完全対応-

探索アルゴリズムに関する問題は頻出です。それぞれの特徴を覚えておきましょう。

線形探索法

探索対象のデータ群の先頭から順に値を比較していく方法。データ群が整列されていなくても探索できるが、使用頻度が高い順に整列されていると少ない回数で目的のデータを探索することが可能になる。
平均比較回数:(N＋1)／2、最大比較回数:N

2分探索法

探索データが昇順または降順に整列されているときに用いる方法。データ中央値と探索対象のデータを比較し、その大小により探索範囲を1/2ずつ狭めていくことで線形探索と比べて効率よく探索することが可能。バイナリサーチとも呼ばれる。
平均比較回数:[log₂N]、最大比較回数:[log₂N]＋1

2分探索木を用いた探索法

2分探索と似ていて、2分探索ではあらかじめデータを整列しておくが、2分探索木を用いた探索法ではデータを節が2本の木構造で保持しておく。
平均比較回数:[log₂N]、最大比較回数:[log₂N]＋1

ハッシュ表を用いた探索法

探索データのキー値から、そのデータの格納場所(アドレス)を直接計算する方法。(シノニムが発生しなければ)1回の計算で一意に目的のデータにたどりつくことができる。
1回の探索でいいので、最も計算量が少ない探索法である。

したがって、正解は「イ」です。

※[a]はaを超えない最大の整数を表します。