問題
問69
配列に格納されているデータを探索するときの、探索アルゴリズムに関する記述のうち、適切なものはどれか。
- 2分探索法は、探索対象となる配列の先頭の要素から順に探索する。
- 線形探索法で探索するのに必要な計算量は、探索対象となる配列の要素数に比例する。
- 線形探索法を用いるためには、探索対象となる配列の要素は探索の値で昇順又は降順にソートされている必要がある。
- 探索対象となる配列が同一であれば、探索に必要な計算量は探索する値によらず、2分探索法が線形探索法よりも少ない。
[出典：ITパスポート試験 令和5年度 問69]
スポンサーリンク
正解
正解は「イ」です。
解説
線形探索法（Linear Search）は、配列の先頭から順に目的の要素を探していく方法です。そのため、最悪の場合、全要素を調べる必要があり、計算量は O(n)（要素数に比例）となります。この特徴が、選択肢「イ」の記述と一致するため、正解となります。
選択肢「ア」は誤りです。2分探索法（Binary Search）は、探索対象がソート済みの配列であることが前提となります。配列の先頭から順に探索するのではなく、中央の要素と比較しながら探索範囲を絞っていく方法です。
選択肢「ウ」は誤りです。線形探索法は ソートが不要な探索方法であり、データがランダムに並んでいても使用できます。逆に、2分探索法はデータがソートされていないと機能しません。
選択肢「エ」は誤りです。2分探索法の計算量はO(log n)であり、線形探索法のO(n)よりも少ない計算量で済みます。ただし、2分探索法が常に線形探索より高速というわけではなく、配列の小さなデータセットでは線形探索のほうが効率的な場合もあります。
難易度
普通
探索アルゴリズムの基本的な知識を問う問題ですが、線形探索と2分探索の違いを正確に理解していないと間違いやすいです。そのため、難易度は普通としました。
スポンサーリンク
用語補足
線形探索法：
配列の先頭から順に目的の要素を探す探索アルゴリズムです。ソートが不要で、どのようなデータにも適用可能ですが、要素数が増えると探索時間が増加します。
2分探索法：
配列がソートされている場合に使用できる探索アルゴリズムです。中央の要素を基準にして探索範囲を半分に分割しながら探すため、高速に探索できます。
対策
- 線形探索法と2分探索法の違いを明確に理解することが重要です。特に、2分探索法を使用するにはソートが必要であることを覚えておきましょう。
- 計算量の違いを理解し、それぞれの探索方法がどのような場面で適しているかを学習しましょう。
- 実際にプログラムを書いて、線形探索法と2分探索法の挙動の違いを体験してみると理解が深まります。
