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

配列のデータを探索するアルゴリズムには、代表的なものとして 線形探索法 と 2分探索法 があります。

線形探索法 は、配列の先頭から順に目的のデータを探す方法です。データの並び順（ソートの有無）に関係なく探索が可能ですが、探索に必要な計算量（比較回数）は配列の要素数 $N$ に比例して大きくなります（オーダー記法では $O(N)$ と表されます）。したがって、選択肢「イ」が適切です。

各選択肢の解説

• ア: 誤り。配列の先頭の要素から順に探索するのは 線形探索法 です。2分探索法は、探索範囲の中央の値と比較し、探索範囲を半分に絞り込みながら探索を行う手法です。
• イ: 正しい。線形探索法で探索するのに必要な計算量は、探索対象となる配列の要素数に比例します。
• ウ: 誤り。探索対象の配列が昇順または降順にソート（整列）されている必要があるのは 2分探索法 です。線形探索法はソートされていなくても使用できます。
• エ: 誤り。2分探索法の最大計算量は $O(\log N)$ であり、線形探索法の $O(N)$ よりも一般的には計算量が少なく済みますが、「探索する値によらず少ない」わけではありません。例えば、探している値が配列の先頭にある場合、線形探索法は1回の比較で見つかりますが、2分探索法は中央から探索を始めるため、線形探索法よりも計算量が多くなる場合があります。