基本情報 平成29年度 秋期 問7：テクノロジ系に関する問題

答えは c です（注：本問の正解は「昇順に整列された配列」で2分探索が使える、という趣旨）。

2分探索＝真ん中を見て「もっと上か下か」を判断し、半分ずつ範囲を絞る探索法。辞書で言葉を引くときに真ん中のページを開いて「もっと前か後ろか」を判断するのと同じです。

👉 覚え方：ソート済み（順番に並んでる）でないと2分探索は使えない！

ほかの選択肢：a ハッシュ＝計算で一発／b 昇順配列＝2分探索の典型適用先／d はOCR乱れだが概念上は連結リストなど順次走査向き。

なぜこれが正解か

2分探索はソート済みかつランダムアクセス可能なデータ構造でこそ最大効果を発揮する。手順は (1) 中央要素と比較、(2) 探索値が小さければ左半分、大きければ右半分に範囲を限定、(3) 範囲が1要素以下になるまで繰り返し。計算量O(log n)で線形探索O(n)より高速。

各選択肢の解説（一般論）

• ハッシュ配置：O(1)平均で取得できるがハッシュ探索専用で2分探索には不向き（順序がない）。
• 昇順整列の配列：2分探索の最適適用先 → 正解の典型。
• セルのアドレス順配置：実体配列であれば順次探索向き。
• ランダム配置：線形探索しか使えない。

覚え方・ひっかけ注意

2分探索の前提は「ソート済み配列（ランダムアクセス可能）」。連結リストは中央要素のアクセスがO(n)なので2分探索は不向き。木構造なら二分探索木（BST）で同等の探索が可能、自己平衡木（AVL、赤黒木）でO(log n)を保証。

理論的背景

2分探索（binary search）の計算量は T(n)=T(n/2)+O(1) より O(log₂ n)。比較回数の理論下限は決定木の高さ ⌈log₂(n+1)⌉ で、2分探索はこれを達成する比較ベース探索の最適アルゴリズム。線形探索O(n)、ハッシュ探索O(1)平均との使い分けは「順序情報の活用」「インデックスの追加コスト」「衝突耐性」で決まる。

派生アルゴリズム

• 補間探索（interpolation search）：データが一様分布なら平均O(log log n)、最悪O(n)。
• 指数探索（exponential search）：未知サイズの配列で範囲を倍々に拡げ、見つけたら2分探索。
• 2分挿入ソート：ソート中に挿入位置を2分探索で決定するが、移動コストは依然O(n)。

データ構造別の探索性能

| 構造 | 探索 | 挿入 | 削除 |

|---|---|---|---|

| ソート済み配列 | O(log n)（2分） | O(n) | O(n) |

| 連結リスト | O(n) | O(1)位置既知 | O(1)位置既知 |

| 二分探索木（平均） | O(log n) | O(log n) | O(log n) |

| 平衡木（AVL/RB） | O(log n)保証 | O(log n) | O(log n) |

| ハッシュ表 | O(1)平均 | O(1)平均 | O(1)平均 |

| B+木（DB索引） | O(log n) | O(log n) | O(log n) |

実装の落とし穴

• 中央計算 `(low+high)/2`：オーバーフロー対策で `low + (high-low)/2` が安全。Java SDKでも2006年に修正された有名バグ。
• 境界条件：`while (low <= high)` か `while (low < high)` でループ脱出条件が変わる。重複要素や下限・上限探索（lower_bound/upper_bound）で実装が分岐。
• 浮動小数点探索：精度問題で `(high-low) < ε` を終了条件にする。

試験での位置づけ

FE「アルゴリズム」分野の超頻出。2分探索の計算量計算、適用条件、線形探索/ハッシュ探索との比較は毎期出題。応用情報・データベーススペシャリストではB+木索引設計、範囲検索の効率化まで踏み込む。

選択肢の発展補足

ハッシュ配置は範囲検索には不向き（順序情報がない）。範囲検索が必要ならソート済み配列＋2分探索またはB+木が選択肢。リアルワールドではDBのインデックス選定でこの判断が重要。