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

2分探索での中央値計算式の決定【午前2 解説】

要点まとめ

• 結論：探索区間の中点を整数添字で取るため、$m=(x+y)/2$（“/”は小数点以下切捨て）が正解です。
• 根拠：昇順配列の各反復で添字の中間を基準に比較し、区間を左右に半分に分割する処理だからです。
• 差がつくポイント：言語の整数除算やオーバーフローに注意し、実装では

  (x+y)//2

  か安全に

  x + (y-x)//2

  を使うと良いです。

正解の理由

よくある誤解

• 「$(x+y)/2$ ではなく $(x+y)$ をそのまま代入すればよい」という誤解：整数添字が必要なので中点を取らないと範囲が適切に狭まらない。
• 「(x-y)/2 や (y-x)/2 が中点」：これらは差の半分であり、左端や右端からのオフセットを表すが直接中点の添字にはならない。
• 実装上のオーバーフロー無視：$x+y$ が大きいと加算でオーバーフローする言語があるため、安全な計算式を知らないとバグになる。

解法ステップ

1. 初期化：$x\leftarrow 1$, $y\leftarrow n$。
2. ループ開始：$x:y$ を比較する判断に進む（$x>y$ なら存在しないとして $m\leftarrow 0$ 終了）。
3. 中点計算：$m\leftarrow (x+y)/2$（小数切捨て）。
4. 比較：$k$ と $A(m)$ を比較する。
   • $k=A(m)$ の場合：$m$ を返して終了。
   • $k<A(m)$ の場合：右端を更新 $y\leftarrow m-1$。
   • $k>A(m)$ の場合：左端を更新 $x\leftarrow m+1$。
5. ステップ2へ戻る。存在しなければ最終的に $m=0$。

# Python での典型的な中点計算（整数除算）
x, y = 1, n
while x <= y:
    m = (x + y) // 2        # これが図の (x+y)/2（切捨て）
    if A[m] == k:
        return m
    elif A[m] > k:
        y = m - 1
    else:
        x = m + 1
# 見つからなければ return 0

選択肢別の誤答解説

• ア: $(x+y)\to m$
  • 誤り。これは中点計算にならず、添字が区間の合計となって範囲縮小の意味を成しません。
• イ: $(x+y)/2→m
  • 正解。区間の中点を整数添字で得る式で、図の動作（左右半分に分割）と一致します。
• ウ: $(x-y)/2\to m$
  • 誤り。これは区間長の半分（左端との差）になるため、直接的に中点の添字にはならず誤用すると負や不正な添字になる可能性があります。
• エ: $(y-x)/2\to m$
  • 誤り。上と同様に区間幅の半分を表すだけで、中点の絶対位置を示していません（左端を加味していない）。

補足コラム

• 実装上の注意点：C系言語などで

  m = (x + y) / 2

  をそのまま使うと整数のオーバーフローでバグになることがあります。安全な書き方は

  m = x + (y - x) / 2

  （整数演算）または

  m = x + (y - x) // 2

  （Python）です。
• 中点の取り方には「下中点（floor）」と「上中点（ceil）」があり、境界処理やループ条件によって使い分けます。本問の流れ（$y\leftarrow m-1$, $x\leftarrow m+1$）は下中点を想定しています。

FAQ

(x+y)//2

x + (y-x)//2