問69
頻出度★★☆
配列に格納されているデータを探索するときの, 探索アルゴリズムに関する記述のうち, 適切なものはどれか。
令和5年度 ITパスポート試験 問69
この問題の解説と、これまでの解答の記録です。
解説
問 69
不正解ア
配列の先頭の要素から順に探索するのは線形探索法の動作である。2分探索法は、ソート済み配列の中央の要素と比較し、大小関係から探索範囲を半分ずつ絞り込んでいく方式なので、先頭から順番には調べない。算法の取り違えで誤り。
- イ
正解 正解はイ。線形探索法は配列の先頭から1要素ずつ順に目的の値と比較していく方式で、最悪の場合は末尾まで全要素を調べる。要素数をnとすると比較回数は最大n回、平均でもnに比例するため、計算量はオーダーでO(n)、つまり配列の要素数に比例する。よって「線形探索法で探索するのに必要な計算量は、探索対象となる配列の要素数に比例する」は適切な記述である。
不正解ウ
要素が昇順または降順にソートされている必要があるのは2分探索法である。線形探索法は先頭から順に全要素を確認するだけなので、ソートされていない配列でもそのまま使える。要件が逆になっており誤り。
不正解エ
「探索する値によらず」常に2分探索法のほうが計算量が少ないとは限らない。例えば目的の値が配列の先頭付近にある場合、線形探索法は1回ないし数回の比較で見つかるのに対し、2分探索法は中央から絞り込むため必ずしも少ない比較で済まない。探索する値や位置によって優劣は変わるため誤り。
ここがポイント
- 線形探索法は先頭から順に比較する単純な方式で、計算量はO(n)（要素数に比例）。事前のソートは不要。
- 2分探索法はソート済み配列が前提で、中央要素との比較により探索範囲を半分ずつ絞るためO(log n)と高速だが、目的値が先頭付近にあるなどの場合は線形探索が有利になることもある。
用語