応用情報技術者 2011年 秋期 午前2 問08

二分探索のループ条件【午前2解説】

正解の理由

解法ステップ

1. 配列が昇順でソートされているため、中央値 center を計算して比較し、探索範囲を半分にする二分探索の基本に従う。
2. ループを継続すべきときは「未発見で、かつまだ探索すべき要素が残っている場合」であり、探索すべき要素が残っていることは $left\le right$ で判定する。
3. 各反復で center ← (left + right) ÷ 2（小数点以下切り捨て）を計算し、X[center] と探索値を比較する。
   • 小さいとき： left ← center + 1
   • 等しいとき： sch ← center（探索成功、ループ条件の sch == −1 が false になり終了）
   • 大きいとき： right ← center − 1
4. ループを抜けたら sch を表示（見つからなければ -1 のまま）。

選択肢別の誤答解説

• ア: left < right
  left < right は「範囲に2以上の要素があるときのみ継続」する条件です。これだと範囲がちょうど1要素（$left=right$）のときループを行わず、その単独要素の比較を行わないため、存在する要素を見逃す可能性があります。従って不適切です。
• イ: left ≦ right
  これは正答です。範囲に1要素ある場合（$left=right$）もループを継続して比較を行うため、正しく動作します。流れ図の中心計算と左右更新（center ± 1）と組み合わせると、探索が適切に収束します。
• ウ: left + 1 < right
  left + 1 < right は right − left ≥ 2、つまり「範囲が3要素以上のときのみ継続」する条件に相当します。これでは範囲が1要素や2要素のときにループを中断してしまい、正しい検索結果を得られません。
• エ: left + 1 ≦ right
  left + 1 ≦ right は right − left ≥ 1、すなわち「範囲が2要素以上のとき継続」する条件です。範囲が2要素のときは継続しますが、範囲が1要素（$right-left=0$）のときはループを終了してしまいます。したがって単一要素を検査できず、誤検出を招きます。

よくある誤解

• 等号の有無を軽視する誤り：while の条件で ≤ を使うべきか < を使うべきか迷い、単一要素の検査を抜かすミスが多いです。二分探索では人為的な off-by-one を招きやすいので注意してください。
• center の算出で切り捨て方を混同：中心計算は整数除算（切り捨て）で行うこと。言語によっては負数の切り捨て挙動が異なるので注意が必要です。
• 中央値計算のオーバーフローを無視：大きな配列で (left + right) が整数の上限を超える場合があります。安全には center ← left + (right - left) ÷ 2 を用いる実装が好まれます。

補足コラム

• ループ条件を while (left <= right) にしておけば、見つかれば即座に sch を更新してループを抜ける設計と自然に合います。別の実装スタイルとして while (left < right) を用いることもありますが、その場合は center の偏り（左寄せ／右寄せ）やループ内の更新法を工夫して、最終的に残る1要素を別途チェックする必要があります。
• 中央値計算のオーバーフロー回避例：center = left + (right - left) // 2

def binary_search(X, target):
    sch = -1
    left = 0
    right = len(X) - 1
    while sch == -1 and left <= right:  # <mark>イ</mark> に対応
        center = left + (right - left) // 2
        if X[center] < target:
            left = center + 1
        elif X[center] == target:
            sch = center
        else:
            right = center - 1
    return sch

FAQ