基本情報技術者 2014年 秋期 午前（科目A） 問06

2分探索に関する記述【午前2 解説】

要点まとめ

• 結論→2分探索（バイナリサーチ）は対象が整列されていることが前提で、整列のない配列では適用不可です。
• 根拠→探索は必ず中央要素と比較して探索範囲を半分に絞るため、順序性がないと正しく半分に分割できません。
• 差がつくポイント→比較回数は概ね $$\begin{gathered} lfloor \\ lo{g}_{2}n \\ rfloor+1 \end{gathered}$$ 程度で、境界処理や初期・終了条件の実装ミスで失点しやすいです。

正解の理由

よくある誤解

• 「先頭から順に見ていく方が単純だから正しい」と考える誤解：これは線形探索の説明で、二分探索の特徴とは混同しないこと。
• 「整列は必須ではない」との誤り：一見部分的に絞れるように見えても、整列されていないとどちら側に探索すべきか判断できません。
• 「計算量が常に小さい」との誤解：小さな n や整列コストを考慮すると必ずしも有利ではなく、前処理（整列）コストも評価する必要があります。

解法ステップ

1. 問題文の各選択肢を一つずつ正確に読む。2分探索の前提（整列）と手順（中央比較）を思い出す。
2. 「整列が必要か」「探索開始位置」「計算量」などの観点で各文の真偽を判定する。
3. 計算量表記は対数（log）か線形（n）かを見極め、単位や書式の誤りにも注意する。
4. 実装上の注意点（境界、端点、偶数・奇数の分割）をイメージして選択肢の言葉尻に惑わされない。

選択肢別の誤答解説

• ア: 2分探索するデータ列は整列されている必要がある。
  → 正しい。二分探索は整列された配列でのみ成立します。整列の有無を見抜けるかが肝。
• イ: 2分探索は線形探索よりも常に速く探索できる。
  → 誤り。理論上は大きな n で $$\begin{gathered} O( \\ logn) \end{gathered}$$ が有利ですが、n が小さい場合や整列のための前処理が必要な場合は総コストで劣ることがあります。
• ウ: 2分探索は探索をデータ列の先頭から開始する。
  → 誤り（問題文の正答指定は ウ ですが実際は不正確）。二分探索は中央要素から比較を開始します。先頭開始は線形探索の手法です。
• エ: n個のデータの2分探索に要する比較回数は、n10g2nに比例する。
  → 誤り。正しくは比較回数は概ね $$\begin{gathered} Theta( \\ lo{g}_{2}n) \end{gathered}$$（対数）に比例します。表記が破損しているか誤記があります。

補足コラム

• 比較回数の目安：最悪ケースでの比較回数は $$\begin{gathered} lfloor \\ lo{g}_{2}n \\ rfloor+1 \end{gathered}$$ 程度です。例えば n=16 なら最大比較回数は 5 回になります。
• 整列済みデータが頻繁に検索される場合、事前に整列（例えば O(n log n)）しておくことで多数回の探索でトータルコストが有利になります。
• 実装上の注意点：整数の中点計算でオーバーフローしうるため、mid を (low + high) // 2 の代わりに low + (high - low) // 2 とするのが安全です。

def binary_search(arr, target):
    low, high = 0, len(arr) - 1
    while low <= high:
        mid = low + (high - low) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1

FAQ