アルゴリズムとプログラミング (全23問中5問目)
No.5
配列に格納されているデータを探索するときの，探索アルゴリズムに関する記述のうち，適切なものはどれか。
出典：令和5年春期 問69
- 2分探索法は，探索対象となる配列の先頭の要素から順に探索する。
- 線形探索法で探索するのに必要な計算量は，探索対象となる配列の要素数に比例する。
- 線形探索法を用いるためには，探索対象となる配列の要素は要素の値で昇順又は降順にソートされている必要がある。
- 探索対象となる配列が同一であれば，探索に必要な計算量は探索する値によらず，2分探索法が線形探索法よりも少ない。
分類
テクノロジ系 » アルゴリズムとプログラミング » アルゴリズムとプログラミング
正解
イ
解説
探索アルゴリズムは、データ群の中から目的のデータを探し出すアルゴリズムです。代表的な探索アルゴリズムとして、線形探索法、2分探索法、ハッシュ法があります。
- 線形探索法
- データ群の先頭から1つずつ順に値を比較していく方法。データ群が整列されていなくても探索できるが、平均比較回数はデータの総数の半分なので探索効率は悪い
- 2分探索法
- 要素が昇順または降順に整列されたデータ群に対して、探索範囲を2分の1に狭めることを繰り返して目的のデータを探索する方法。①探索範囲の中央に位置する値と目的のデータを比較する、②目的のデータの方が小さければ中央から探索範囲の最後までを、目的のデータの方が大きければ探索範囲の最初から中央まで探索範囲から除外して、探索範囲を2分の1にする、という操作を再帰的に繰り返して効率よく目的のデータを探すことができる
- ハッシュ法
- 目的のデータの探索キーをハッシュ関数にかけて、データの格納位置を直接計算する方法。基本的に1回の探索で目的の値にたどり着くことができる
- 配列の先頭の要素から順に探索するのは線形探索法です。2分探索法は、①探索範囲の中央に位置する値と比較する、②探索範囲を2分の1に狭める、ことを繰り返して探索する方法です。
- 正しい。要素がN個であるデータ群から線形探索法で探すとき、目的のデータが1番最初にあれば1回、最後にあればN回の比較が必要となります。どこに目的のデータがあるかはランダムなので、線形探索法の平均比較回数はN－12回となります（データ総数のおよそ半分）。データ群が多いほど平均比較回数も増える比例関係にあります。
- 線形探索法ではデータ群は整列されている必要はありません。データ群をあらかじめ整列しておく必要があるのは2分探索法です。
- 探索対象が同一である場合、2分探索法は線形探索法よりも平均比較回数が少なくなります。平均比較回数ですので、たまたま配列の先頭のほうに目的のデータが存在した場合など、探索する値によっては線形探索法のほうが少ない計算量で探索できることもあります。また、2分探索法では事前に整列をしておく必要があるので、その分の計算量が必要になる面で不利です。