令和5年度 ITパスポート試験 問69
テクノロジ／アルゴリズム配列に格納されているデータを探索するときの，探索アルゴリズムに関する記述のうち，適切なものはどれか。
出典：令和5年度 ITパスポート試験 問69
- ア2分探索法は，探索対象となる配列の先頭の要素から順に探索する。
- イ線形探索法で探索するのに必要な計算量は，探索対象となる配列の要素数に比例する。
- ウ線形探索法を用いるためには，探索対象となる配列の要素は要素の値で昇順又は降順にソートされている必要がある。
- エ探索対象となる配列が同一であれば，探索に必要な計算量は探索する値によらず，2分探索法が線形探索法よりも少ない。
正解：イ
解説
線形探索法は先頭から順に 1 つずつ調べる方法で，最悪の場合は全要素を調べるため，必要な計算量は要素数に比例します。2 分探索法は，ソート済みの配列の中央の要素と比べて探索範囲を半分ずつに絞る方法で，先頭からは探索しません。また，探索する値によっては（たとえば配列の先頭にある値なら）線形探索法のほうが早く見つかることもあります。
選択肢ごとの解説
- ア誤り。2 分探索法は，配列の中央の要素と比べて探索範囲を半分に絞っていく方法で，先頭から順に探索するのは線形探索法です。
- イ正しい。線形探索法は先頭から順に調べるので，計算量は要素数に比例します。
- ウ誤り。ソートされている必要があるのは 2 分探索法で，線形探索法はソートされていなくても使えます。
- エ誤り。探索する値の位置によっては，線形探索法のほうが少ない比較回数で見つかる場合もあるので，常に 2 分探索法が少ないとはいえません。