ITパスポート過去問 令和5年度（2023年）問69
配列に格納されているデータを探索するときの，探索アルゴリズムに関する記述のうち，適切なものはどれか。
選択肢
- ア：2分探索法は，探索対象となる配列の先頭の要素から順に探索する。
- イ：線形探索法で探索するのに必要な計算量は，探索対象となる配列の要素数に比例する。
- ウ：線形探索法を用いるためには，探索対象となる配列の要素は要素の値で昇順又は降順にソートされている必要がある。
- エ：探索対象となる配列が同一であれば，探索に必要な計算量は探索する値によらず，2分探索法が線形探索法よりも少ない。
- ア
- イ
- ウ
- エ
正解と解き方・学習ポイント（AI解説）
線形探索法は配列の先頭から順に比較して探す方法で、比較回数は要素数に応じて増えるため計算量は要素数に比例します。2分探索法はソート済み配列を前提に、中央要素との比較で探索範囲を半分ずつ絞り込む方法です。したがって、線形探索法の計算量が要素数に比例するという記述が適切です。
Point
線形探索法と2分探索法について、次の2点を区別して理解できているかを確認する問題です。
-
探索手順の違い（先頭から順か、中央から範囲を絞るか）
-
前提条件と計算量の基本（線形探索はO(n)、2分探索は整列が必要でO(log n)）
解くために必要な知識
この問題を解くには、線形探索法と2分探索法の手順、前提条件、計算量（O記法）を理解している必要があります。
用語の整理
| 用語 | 意味 |
|---|---|
| 線形探索法 | 配列（またはリスト）の先頭から順に比較して目的の値を探す方法です。未整列でも使えます。 |
| 2分探索法 | 整列済みデータに対して、中央要素との比較で探索範囲を半分に絞り込みながら探す方法です。 |
| 計算量（O記法） | 要素数nが増えたときに、比較回数などの処理量がどの程度増えるかを表す表記です。 |
線形探索法の計算量
-
最悪の場合: n回程度比較します。
-
そのため、計算量はO(n)として扱われます。
2分探索法の計算量と前提
-
前提条件: 配列が昇順または降順に整列されている必要があります。
-
探索範囲を半分にしていくため、計算量はO(log n)として扱われます。
他の選択肢に出てくる用語
| 用語 | 意味 |
|---|---|
| ソート（整列） | データを昇順・降順などの規則で並べ替えることです。 |
問題の解法手順
各選択肢の整理
| 選択肢 | 内容 | 正誤 | 理由 |
|---|---|---|---|
| ア | 2分探索法は先頭から順に探索する | 誤り | 先頭から順に探索するのは線形探索法です。2分探索法は中央の要素から比較し、探索範囲を半分に絞ります。 |
| イ | 線形探索法の計算量は要素数に比例する | 正しい | 最悪の場合に全要素を比較するため、比較回数はn回程度となり、計算量はO(n)です。 |
| ウ | 線形探索法にはソート済みの配列が必要 | 誤り | ソートが必要なのは2分探索法です。線形探索法は並び順に依存しません。 |
| エ | 2分探索法は探索する値によらず線形探索法より計算量が少ない | 誤り | 探す値が先頭付近にある場合、線形探索法は1回など少ない比較で見つかることがあり、2分探索法より比較回数が少なくなる場合があります。 |
選択肢ごとの解説
- ア：不正解
2分探索法は、整列済みの配列に対して中央の要素と比較し、目的の値があり得る範囲を半分に絞り込みます。先頭から順に比較していく方法は線形探索法です。
- イ：正解
線形探索法は先頭から順に比較するため、要素数がnのとき最悪でn回程度の比較が必要です。したがって処理量は要素数に比例し、計算量は一般にO(n)となります。
- ウ：不正解
線形探索法は未整列の配列でも先頭から順に比較できる方法です。整列が必要なのは、並び順を使って探索範囲を絞る2分探索法です。
- エ：不正解
2分探索法は整列済みであることが前提です。また線形探索法は探索値が先頭付近にある場合、比較回数が少なく済みます。そのため探索する値によっては線形探索法の方が比較回数が少ない場合があり、「値によらず常に2分探索法が少ない」は不適切です。
まとめ
線形探索法は配列の先頭から順に比較して探す方法で、比較回数は要素数に応じて増えるため計算量は要素数に比例します。2分探索法はソート済み配列を前提に、中央要素との比較で探索範囲を半分ずつ絞り込む方法です。したがって、線形探索法の計算量が要素数に比例するという記述が適切です。
テクノロジ系 > 基礎理論 > アルゴリズムとプログラミング
2分探索法は、整列済みの配列に対して中央の要素と比較し、目的の値があり得る範囲を半分に絞り込みます。先頭から順に比較していく方法は線形探索法です。
線形探索法は先頭から順に比較するため、要素数がnのとき最悪でn回程度の比較が必要です。したがって処理量は要素数に比例し、計算量は一般にO(n)となります。
線形探索法は未整列の配列でも先頭から順に比較できる方法です。整列が必要なのは、並び順を使って探索範囲を絞る2分探索法です。
2分探索法は整列済みであることが前提です。また線形探索法は探索値が先頭付近にある場合、比較回数が少なく済みます。そのため探索する値によっては線形探索法の方が比較回数が少ない場合があり、「値によらず常に2分探索法が少ない」は不適切です。