配列探索における線形探索法と2分探索法の特徴(計算量と前提条件)

正解は イ です。 線形探索法は、配列の 先頭から順に 1つずつ比べる方法です。要素数が2倍になれば比較回数(最大・平均)もおよそ2倍になるので、計算量は 要素数に比例 します。 項目 線形探索法 2分探索法 探し方 先頭から順に比べる 中央の要素と比べ、範囲を半分に絞る 前提条件 なし(未整列でもよい) 昇順か降順に整列済み 比較回数の目安 最大 n 回(n に比例) 最大 約 $\log_2 n$ 回 先頭から順に探索するのは線形探索法です。2分探索法は中央の要素から比べます。 整列されている必要があるのは2分探索法です。線形探索法は未整列でも使えます。 探す値が先頭付近にあれば、線形探索法は1〜2回の比較で見つかります。値によっては線形探索法の方が少なく済むので「値によらず」は誤りです。

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

出典令和5年度 ITパスポート試験 公開問題 問69
ア
2分探索法は,探索対象となる配列の先頭の要素から順に探索する。
イ
線形探索法で探索するのに必要な計算量は,探索対象となる配列の要素数に比例する。
ウ
線形探索法を用いるためには,探索対象となる配列の要素は要素の値で昇順又は降順にソートされている必要がある。
エ
探索対象となる配列が同一であれば,探索に必要な計算量は探索する値によらず,2分探索法が線形探索法よりも少ない。