ITパスポート試験 ITパスポート 2023年 (令和5年) 問69: 配列に格納されているデータを探索するときの,探索アルゴリズムに関する記述のうち,適切なものはどれか。

正解

イ. 線形探索法で探索するのに必要な計算量は,探索対象となる配列の要素数に比例する。

正答率 70.9%（1,244人中 882人が正解）

問題の解説

線形探索法は配列の先頭から順に調べていく方法で、最悪の場合は全ての要素を調べるため、必要な計算量は要素数に比例する。2分探索法は、整列済みの配列の中央の要素と比べて探索範囲を半分ずつ絞る方法で、要素が多いほど有利だが、探す値が先頭付近にあれば線形探索法の方が早く見つかることもある。

選択肢ごとの解説

• ア先頭から順に調べるのは線形探索法である。2分探索法は、中央の要素と比較して探索範囲を半分ずつ絞り込む。
• イ正しい。先頭から順に調べるので、最悪の場合は全ての要素を調べることになり、計算量は要素数に比例する。
• ウ要素が昇順または降順に整列されている必要があるのは2分探索法である。線形探索法は並び順を問わない。
• エ探す値が配列の先頭付近にあれば、線形探索法の方が少ない比較で見つかる。値によらず常に2分探索法が少ないとはいえない。