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

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

正解の理由

解法ステップ

1. 問題文の各選択肢を読み、2分探索の前提条件を思い出す（整列されていること）。
2. ア〜エそれぞれを二分探索の特徴と照らし合わせる：
   • ア：整列が必要か？ → 必要 → 正しい。
   • イ：常に速いか？ → 条件付き（整列済みで比較回数は小さいが整列コスト無視は不可） → 誤り。
   • ウ：先頭から開始するか？ → いいえ、中央値から開始 → 誤り。
   • エ：比較回数は $n{\log }_{2}n$ か？ → いいえ、二分探索は $O(\log n)$ → 誤り。
3. 正解を選ぶ：ア。

選択肢別の誤答解説

• ア: 2分探索するデータ列は整列されている必要がある。 → 正解。整列が前提であることを明確に示す文言です。
• イ: 2分探索は線形探索よりも常に速く探索できる。→ 誤り。整列済みの配列に対しては比較回数で優れるが、整列の前処理を要する場合や小さなnでは一概に「常に速い」とは言えません。
• ウ: 2分探索は探索をデータ列の先頭から開始する。→ 誤り。二分探索は中央（中央値）を起点に左右を半分に絞っていきます。先頭から順に見るのは線形探索の特徴です。
• エ: n個のデータの2分探索に要する比較回数は、$n{\log }_{2}n$に比例する。→ 誤り。単純な二分探索の比較回数は $O(\log n)$、$n{\log }_{2}n$ は主に比較ソートの計算量です。

よくある誤解

1. 2分探索は常に線形探索より速い：誤り。データが整列されていない場合は二分探索が使えず、整列に要するコストを考慮すると全体では線形探索より遅くなる場合があります。
2. 2分探索は先頭から順に調べる探索である：誤解。二分探索は中央から開始して範囲を半分に絞る方式で、先頭から順に見ていく線形探索とは異なります。
3. 比較回数が $n{\log }_{2}n$：混同の典型。2分探索単体の比較回数は $O(\log n)$（例えば最大で $\lceil {\log }_{2}n\rceil$ 回程度）であり、$n{\log }_{2}n$ は典型的にソートアルゴリズムの時間（比較ソート）に関連します。

補足コラム

• 実装上の注意点：配列の両端インデックス（low, high）やミドルインデックスの計算でオーバーフローを避けるため、mid = low + (high - low) // 2 のように書くのが安全です。
• 安定性・事前ソートのコスト：探索アルゴリズムの性能評価では「探索単体のコスト」と「前処理（ソート）を含めた全体コスト」を区別することが重要です。検索回数だけでなく、前処理の時間も考慮すると適切な選択ができます。
• 実用場面：静的なデータ（頻繁に更新されない）に対しては二分探索が有効、動的な挿入・削除が頻繁に起きる場合は平衡二分木やハッシュ表などを検討します。

FAQ