ITパスポート 2023年 問69

配列の探索アルゴリズムに関する記述【ITパスポート 解説】

正解の理由

解法ステップ

1. 用語を確認する
   • 配列：順序付けて並んだデータの集合（インデックスでアクセスできる）。
   • 線形探索法（linear search）：先頭から順に要素を一つずつ比較して探す。
   • 2分探索法（二分探索、binary search）：配列がソート（並び替え）されていることを前提に、中央付近の要素と比較して探索範囲を半分に絞る。
2. 各選択肢が示す条件と計算量の知識を照合する。
3. 線形探索の比較回数の傾向（最悪で n、平均で約 n/2）と、二分探索の条件（ソート必須、計算量は $O(\log n)$）を用いて判断する。
4. 最も整合する記述を選ぶ（今回は イ）。

選択肢別の誤答解説

• ア: 「2分探索法は、探索対象となる配列の先頭の要素から順に探索する。」
  → 誤り。二分探索（binary search）は配列がソートされていることが前提で、必ず中央付近の要素と比較して探索範囲を半分にしていきます。先頭から順に探すのは線形探索です。
• イ: 「線形探索法で探索するのに必要な計算量は、探索対象となる配列の要素数に比例する。」
  → 正しい。線形探索は最悪で n 回、平均で約 (n+1)/2 回の比較が必要になり、計算量は $O(n)$ と表されます。
• ウ: 「線形探索法を用いるためには、探索対象となる配列の要素は要素の値で昇順又は降順にソートされている必要がある。」
  → 誤り。線形探索はソートされている必要はありません。ソート不要で単純に先頭から見ていける点が利点です。ソートが必要なのは二分探索です。
• エ: 「探索対象となる配列が同一であれば、探索に必要な計算量は探索する値によらず、2分探索法が線形探索法よりも少ない。」
  → 誤り。探索に必要な作業量が「探索する値によらない」というのは正確ではありません。線形探索は探す値が先頭にあると少ない比較で済み、最後や存在しない場合は多くの比較が必要です（位置に依存します）。二分探索は確かに計算量の成長は $O(\log n)$ と小さいですが、前提として配列がソートされていることが必要ですし、探索コストの絶対値が常に線形探索より小さいとは限りません（例えば n が小さいときや、線形探索で見つかる位置が非常に早いときなど）。

よくある誤解

1. 「二分探索は常に速い」
   • 誤解です。二分探索は大きなデータで有利ですが、配列がソートされていないと使えません。また、配列サイズが小さい場合は線形探索の方が簡単で速い場合があります。
2. 「計算量（Big O）は実際の時間と同義」
   • 誤解です。計算量は入力サイズに対する増え方の目安です。実行環境や定数因子、データの分布によって実時間は変わります。
3. 「線形探索は無条件に悪い」
   • 誤解です。実装は単純で、配列がソートされていない場合やデータが少ない場合、あるいは最初の方に見つかる期待があるなら有効です。

補足コラム

• 比較回数の具体例（配列長 n = 10）
  • 線形探索：最悪で 10 回、平均で約 5.5 回（$(n+1)/2$）。
  • 二分探索：最悪で $\lceil {\log }_{2}10\rceil =4$ 回程度の比較で済みます（${\log }_{2}n$ は要素数を2で割る回数の目安）。
• 簡単なコード例（説明用）

  # 線形探索（線形探索法）
  def linear_search(arr, target):
      for i, v in enumerate(arr):
          if v == target:
              return i  # 見つかったインデックス
      return -1  # 見つからない
  
  # 二分探索（配列は昇順にソートされている前提）
  def binary_search(arr, target):
      left, right = 0, len(arr) - 1
      while left <= right:
          mid = (left + right) // 2
          if arr[mid] == target:
              return mid
          elif arr[mid] < target:
              left = mid + 1
          else:
              right = mid - 1
      return -1
  

• 線形探索はソート不要で実用的な場面が多い。二分探索はソートのコスト（ソート自体は $O(n\log n)$ など）も考慮に入れて使うべきです。

FAQ