ITパスポート 令和5年度 問69

✓ これが正解イ 線形探索法で探索するのに必要な計算量は，探索対象となる配列の要素数に比例する。

解説

線形探索法にかかる手間は、配列の要素数に比例します。

線形探索法は、配列の先頭から順に一つずつ見ていき、探している値と同じものが見つかるまで進む方法です。最悪の場合は最後まで見ることになるので、必要な手間は要素数に比例して増えます。これに対し2分探索法は、並び替えてある配列の真ん中と比べて、探す範囲を半分ずつ絞っていく方法です。手間は要素数の増え方に比べてずっと緩やかにしか増えませんが、あらかじめ並び替えてあることが前提になります。どちらが有利かは、探す回数と並び替えの手間を合わせて考えることになります。よって適切なのは、線形探索法で探索するのに必要な計算量は、配列の要素数に比例する、という記述です。

ほかの選択肢の解説

• ア 2分探索法は，探索対象となる配列の先頭の要素から順に探索する。：先頭の要素から順に探索するのは線形探索法のほうです。2分探索法は真ん中と比べて範囲を半分ずつ絞るので、先頭から順に見ていくことはありません。二つの方法の説明が入れ替わっています。あらかじめ並べ替えてあることが前提になるのも、2分探索法のほうです。
• ウ 線形探索法を用いるためには，探索対象となる配列の要素は要素の値で昇順又は降順にソートされている必要がある。：並び替えられている必要があるのは2分探索法のほうです。線形探索法は先頭から順に見るだけなので、並びがばらばらでも使えます。むしろ並び替えの手間が不要な点が、この方法の取りえです。
• エ 探索対象となる配列が同一であれば，探索に必要な計算量は探索する値によらず，2分探索法が線形探索法よりも少ない。：探索する値によらず常に2分探索法のほうが少ない、とは言えません。探している値がたまたま配列の先頭にあれば、線形探索法は一度比べるだけで済みます。平均や最悪の場合の話と、個々の場合の話は区別が必要です。