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

二分探索の前提【午前解説】

正解の理由

解法ステップ

1. 二分探索の前提条件（整列の要否）を思い出す。分割して選択するには順序が必要。
2. 各選択肢の主張がアルゴリズムの性質と符号するかを順に確認する。
   • 探索速度を比較する場合は「常に速い」といえるか（入力の性質や構造によって変わるか）を考える。
   • 探索開始位置や計算量の式が一般的な二分探索の定義と合っているかを検証する。
3. 正しいものを1つ選ぶ（ここでは前提条件が満たされるものが該当）。

選択肢別の誤答解説

• ア: 正。二分探索は要素が整列されている（昇順または降順）ことが前提条件であるため、これが満たされないと適用できません。
• イ: 誤。二分探索は平均・最悪で $O(\log n)$ の時間だが、線形探索（$O(n)$）より「常に速い」とは言えない場面がある。例えばデータが整列されていない場合は二分探索自体が使えない。データ構造や定数係数によって小さい n では線形探索の方が速いこともある。
• ウ: 誤。二分探索はデータ列の先頭から順に比較していく線形探索とは異なり、中央（あるいは区間の中点）から比較を始め、探索区間を半分に狭めていく手法です。
• エ: 誤。比較回数や時間計算量は $n{\log }_{2}n$ ではなく $O(\log n)$。$n{\log }_{2}n$ は典型的にはソートアルゴリズム（例: マージソート、ヒープソート）の時間計算量です。

よくある誤解

• 「二分探索は配列でしか使えない」：ランダムアクセス可能な配列で最も効率的ですが、順次アクセスしかできない連結リストでは位置計算（中央へのアクセス）に追加コストがかかるため実用的でないことがあります。二分探索そのものは「整列された順序付き集合」に対して成立します。
• 「二分探索は必ず線形探索より速い」：小さい n や実装やメモリ局所性の違いで逆になることがあるため、常にという表現は誤りです。
• 「比較回数は正確に $\lceil {\log }_{2}n\rceil$ だ」：正確な最悪比較回数は $\lfloor {\log }_{2}n\rfloor +1$（＝$\lceil {\log }_2(n+1)\rceil$）です。丸め方の扱いに注意してください。

補足コラム

• 最大比較回数の直感的導出：区間の長さを半分にしていくので、k 回の比較で候補は最大で $\lceil n/2^k\rceil$ 個になる。これが 1 以下になる最小の k を求めると、$2^k\ge n+1$ となり、$k\ge {\log }_2(n+1)$。従って整数回数としては $k=\lceil {\log }_2(n+1)\rceil$（同値に $\lfloor {\log }_{2}n\rfloor +1$）が上限になります。
• 二分探索の派生：lower_bound（最初の >= を返す）、upper_bound（最初の > を返す）などは重複要素の取り扱いで便利です。また、降順に整列されている場合は比較の向きを反転すれば同様に使えます。
• 実装上の注意：終端条件や区間の更新（閉区間 vs 半開区間）の扱いを誤ると無限ループやオフバイワンが発生しやすいです。テストケースに n=0, n=1, 四則境界値を含めて検証してください。

def binary_search(a, target):
    lo, hi = 0, len(a) - 1  # 閉区間 [lo, hi]
    while lo <= hi:
        mid = (lo + hi) // 2
        if a[mid] == target:
            return mid
        elif a[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1  # 見つからない

FAQ