ITパスポート試験 令和5年度 公開問題 問69

【正解】イ

線形探索法は、配列の先頭から要素を一つずつ目的の値と比較する方法です。要素数をnとすると、目的の値が末尾にある場合や存在しない場合には、最大でn個の要素を確認します。そのため、探索に必要な計算量は要素数に比例し、O（n）と表されます。

アの説明は誤りです。先頭から順に調べるのは線形探索法です。2分探索法は、整列済みの配列の中央の要素と目的の値を比較し、探索範囲を半分ずつに絞ります。

ウの説明は誤りです。線形探索法では配列を事前にソートする必要はありません。昇順又は降順にソートされている必要があるのは2分探索法です。

エの説明は誤りです。線形探索法の比較回数は、目的の値が先頭にあるか、末尾にあるか、存在しないかによって変わります。2分探索法の比較回数も値の位置によって変わり、目的の値が先頭にある場合などには線形探索法の方が少ないこともあるため、常に2分探索法が少ないとはいえません。

【ポイント】 線形探索法の計算量はO（n）で、未整列の配列にも使用できます。 2分探索法の計算量はO（log n）ですが、配列があらかじめ整列されている必要があります。 「常に」や「探索する値によらず」という断定表現にも注意します。