配列に格納されているデータを探索するときの、探索アルゴリズムに関する記述のうち、適切なものはどれか。
- ア. 2分探索法は、探索対象となる配列の先頭の要素から順に探索する。
- イ. 線形探索法で探索するのに必要な計算量は、探索対象となる配列の要素数に比例する。
- ウ. 線形探索法を用いるためには、探索対象となる配列の要素は要素の値で昇順又は降順にソートされている必要がある。
- エ. 探索対象となる配列が同一であれば、探索に必要な計算量は探索する値によらず,2分探索法が線形探索法よりも少ない。
【答え】イ
【解説】
各選択肢の解説
ア. 2分探索法は、探索対象となる配列の先頭の要素から順に探索する。
→これは線形探索法（リニアサーチ）の説明。2分探索法（バイナリサーチ）は、配列を中央で分割しながら探索を進める手法です。
イ. 線形探索法で探索するのに必要な計算量は、探索対象となる配列の要素数に比例する。
→ ⭕ 線形探索は最悪の場合（例：目的のデータが最後にある場合）、配列全体を調べる必要があるため、必要な計算量は要素数に比例します。
ウ. 線形探索法を用いるためには、探索対象となる配列の要素は要素の値で昇順又は降順にソートされている必要がある。
→線形探索は先頭から順に比較を行う手法なので、ソート（並び替え）されていなくても使えます。ソート済み配列が前提となるのは2分探索法です。
エ. 探索対象となる配列が同一であれば、探索に必要な計算量は探索する値によらず,2分探索法が線形探索法よりも少ない
→平均的には、2分探索法は線形探索法より計算量が少なく高速ですが、値の位置によっては線形探索のほうが早く見つかる場合もあります（例：目的のデータが先頭の方にある場合など）。また、2分探索には「配列がソート済みであること」が前提なので、その分計算量は多くなります。
以上より、正解はイ.となります。
アルゴリズムとプログラミング1～アルゴリズムと流れ図（フローチャート）～
※やや難問ですが、線形探索法と二分探索法の特徴を理解していれば、何とか解答できる問題です。
