BohYoh.com《第２種情報処理技術者試験》1995年度＝平成7年度・秋期午前問14

第２種情報処理技術者試験

1995年度＝平成7年度・秋期

午前

問14

　探索法に関する記述のうち、誤っているものはどれか。

ア	2分探索法を利用する場合、データは整列されている必要がある。
イ	100件分のデータを2分探索法で探索する場合、最大でも7回の比較によって目的のデータが探索できる。
ウ	線形探索法では、データが整列されていても比較回数が少なくなるとは限らない。
エ	データが10件以内ならば、2分探索法より線形探索法のほうが平均比較回数は少ない。
オ	データの件数を100件から1,000件に増やすと、線形探索法では平均比較回数が10倍に増えるが、2分探索法では2倍以下である。

解答

　エ

解説

●２分探索法は、整列済みの配列の中央に位置する要素と等しいか／大きいか／小さいかの判断を行い、探索すべき範囲を半分ずつに絞り込んでいく探索法であり、探索に要する平均比較回数はlog₂nです。
●線形探索法は、配列の先頭から順に比較を行っていく探索法であり、探索に要する平均比較回数はn / 2です。
　したがって、データが10件以内ならば、2分探索法より線形探索法のほうが平均比較回数は多くなります。