問題プレビューID: dd1cc3b9

問 6

昇順に整列済みの配列要素 $A(1), A(2), \cdots, A(n)$ から， $A(m) = k$ となる配列要素 $A(m)$ の添字 $m$ を 2 分探索法によって見つける処理を図に示す。終了時点で $m = 0$ である場合は， $A(m) = k$ となる要素は存在しない。図中の a に入れる式はどれか。ここで，“/”は，小数点以下を切り捨てる除算を表す。

解説

2分探索法では，探索範囲の中央にある要素の添字を求めて，その要素と探索値 $k$ を比較する。 $x$ が探索範囲の下限， $y$ が上限を表しているので，中央の添字 $m$ は $(x + y)$ を 2 で割った値（小数点以下切捨て）となる。

よって，a に入る式は $(x + y) / 2 \rightarrow m$ である。

したがって，正解は「イ」である。