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

答えは c「顧客番号の昇順に配置されているデータ構造」 です。

2分探索は、真ん中のデータを見て「探している番号はもっと前か後ろか」を判断し、範囲を半分ずつ絞っていく探し方。辞書を真ん中で開いて前後を判断するのと同じです。

そのため、データが番号順に並んでいることが前提。昇順に並んだ c がぴったりです。

👉 覚え方：2分探索は「並べてから半分ずつ」。

ほかの選択肢：a ハッシュ値の位置に置く構造は、計算で場所を直接求めるハッシュ探索向き／b ランダムに並んでいると前後を判断できない／d セルのアドレス順は顧客番号の順とは関係がない。

なぜこれが正解か

正解は c。2分探索は、探索範囲の中央の要素とキーを比べ、キーが小さければ前半、大きければ後半に範囲を絞る操作を繰り返す。この「前か後ろか」の判断ができるのは、データがキーの順に整列しているときだけ。顧客番号の昇順に配置されたデータ構造なら、比較回数は最大でも約 log₂N 回で済む（N=1,000件なら約10回）。

各選択肢の解説

• a：ハッシュ値が指し示す位置にデータを置く構造は、キーからハッシュ関数で格納位置を直接計算するハッシュ探索に使う。並び順は顧客番号の大小と無関係なので2分探索はできない。
• b：ランダムに配置されたデータは大小の判断で範囲を絞れないため、先頭から順に調べる線形探索しか使えない。
• c：キー（顧客番号）の昇順に整列しているので2分探索に適している（正解）。
• d：セルのアドレス順は格納した場所の順であって、顧客番号の順ではない。キーの大小で範囲を絞れないので2分探索には向かない。

覚え方・ひっかけ注意

2分探索の前提は「キーで整列済み」かつ「中央の要素をすぐ取り出せる（配列のように位置を指定してアクセスできる）」こと。連結リストは整列していても中央までたどるのに時間がかかるため2分探索には不向き。計算量は線形探索 O(N)、2分探索 O(log N)、ハッシュ探索は衝突がなければ O(1)。

理論的背景

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)。

データ構造別の探索性能

実装の落とし穴

• 中央計算 `(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のインデックス選定でこの判断が重要。