科目A問69
配列に格納されているデータを探索するときの，探索アルゴリズムに関する記述のうち，適切なものはどれか。
| 2分探索法は，探索対象となる配列の先頭の要素から順に探索する。 | |
| 線形探索法で探索するのに必要な計算量は，探索対象となる配列の要素数に比例する。 | |
| 線形探索法を用いるためには，探索対象となる配列の要素は要素の値で昇順又は降順にソートされている必要がある。 | |
| 探索対象となる配列が同一であれば，探索に必要な計算量は探索する値によらず，2分探索法が線形探索法よりも少ない。 |
『情報処理過去問.com』からiPhoneアプリがリリースされました！！
正解
- イ
解説
探索アルゴリズムは、配列やリストなどのデータ集合から目的の値を見つけ出すための手法であり、代表的なものに線形探索法（Linear Search）と2分探索法（Binary Search）があります。線形探索法は先頭から順に比較する単純な方法で、データが未整列でも利用できますが、計算量はO(n)となり要素数に比例して増加します。一方、2分探索法はデータがあらかじめ昇順または降順に整列されている必要がありますが、探索範囲を半分ずつ絞り込むことで効率的に探索でき、計算量はO(log n)となります。ただし、探索対象の位置によって実際の比較回数は変化するため、アルゴリズムの特性を理解して使い分けることが重要です。
| ア. | 2分探索法は，探索対象となる配列の先頭の要素から順に探索する。 |
| 2分探索法は、中央の要素と比較して探索範囲を半分に絞ることで探索を行うアルゴリズムなので、先頭から順に探索する方法ではなく不適切です。 | |
| イ. | 線形探索法で探索するのに必要な計算量は，探索対象となる配列の要素数に比例する。 |
| 線形探索法の計算量は、要素数に比例して増加するため計算量がO(n)となるアルゴリズム特性なので適切です。 | |
| ウ. | 線形探索法を用いるためには，探索対象となる配列の要素は要素の値で昇順又は降順にソートされている必要がある。 |
| 線形探索法は、データが整列されていなくても利用できる探索アルゴリズムなので、整列が必要という説明は不適切です。 | |
| エ. | 探索対象となる配列が同一であれば，探索に必要な計算量は探索する値によらず，2分探索法が線形探索法よりも少ない。 |
| 探索アルゴリズムの計算量比較は、探索対象や条件によって計算量が変化する特性があるため、常に2分探索法が少ないとは限らず不適切です。 |