令和5年度 ITパスポート 問69 解説
配列に格納されているデータを探索するときの，探索アルゴリズムに関する記述のうち，適切なものはどれか。
- ア2分探索法は，探索対象となる配列の先頭の要素から順に探索する。
- イ線形探索法で探索するのに必要な計算量は，探索対象となる配列の要素数に比例する。
- ウ線形探索法を用いるためには，探索対象となる配列の要素は要素の値で昇順又は降順にソートされている必要がある。
- エ探索対象となる配列が同一であれば，探索に必要な計算量は探索する値によらず，2分探索法が線形探索法よりも少ない。
答えを見る
正解 イ線形探索法で探索するのに必要な計算量は，探索対象となる配列の要素数に比例する。
要点線形探索の計算量は要素数に比例し、整列は不要
解説
線形探索法は先頭から順に1つずつ比べるため、必要な計算量は配列の要素数に比例します。
- ア：先頭から順に探すのは線形探索法で、2分探索法は中央の値と比べて範囲を半分に絞るので誤り。
- ウ：整列済みであることが必要なのは2分探索法で、線形探索法は整列不要なので誤り。
- エ：探す値が先頭付近にあれば線形探索法の方が少ない比較回数で済むこともあり、常に2分探索法が少ないとはいえないので誤り。