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

配列に格納されているデータを探索するときの，探索アルゴリズムに関する記述のうち，適切なものはどれか。

ア	2分探索法は，探索対象となる配列の先頭の要素から順に探索する。
イ	線形探索法で探索するのに必要な計算量は，探索対象となる配列の要素数に比例する。
ウ	線形探索法を用いるためには，探索対象となる配列の要素は要素の値で昇順又は降順にソートされている必要がある。
エ	探索対象となる配列が同一であれば，探索に必要な計算量は探索する値によらず，2分探索法が線形探索法よりも少ない。

◀ 問68　|　▲ 令和5年問題一覧　|　問70 ▶

答え：イ
分野：テクノロジ系 › 基礎理論 › アルゴリズムとプログラミング › アルゴリズムとプログラミング
解説：
データ集合から指定の条件を満たすデータを探し出す操作を「探索」(search)と言います。データの種類や構造に応じて様々な手法が提唱されており，必要な計算時間や記憶容量などの特性が異なります。

「ア」… 誤り。先頭から順に探索する方式は線形探索です。
「イ」… 正解。先頭から順に探索するため要素数に比例して探索時間が伸びます。
「ウ」… 誤り。探索開始前にソート済みである必要があるのは二分探索です。
「エ」… 誤り。探している値がたまたま先頭付近にある場合は線形探索の方が早くなる場合があります。二分探索は事前にソートする計算量も必要なため，探索が一度限りの場合は線形探索より遅い場合があります。