問題6
昇順に整列済みの配列要素 A(1), A(2), …, A(n) から,A(m)=k となる配列要素 A(m) の添字 m を2分探索法によって見つける処理を図に示す。終了時点で m=0 である場合は,A(m)=k となる要素は存在しない。図中の a に入る式はどれか。ここで「/」は,小数点以下を切り捨てる除算を表す。
| ア | (x+y)→m |
| イ | (x+y)/2→m |
| ウ | (x-y)/2→m |
| エ | (y-x)/2→m |
解答・解説を見る
解答：イ
2分探索法は，整列済みの配列から効率よくデータを探索するための方法である。
2分探索法は、整列されたデータの中央の値と対象データを比較し、それより前方にあるか後方にあるかを判断する。
前方にデータがある場合は、前半分のデータの中央のデータと比較し、後方にデータがある場合は、後半分のデータの中央のデータと比較する。
この操作を繰り返すことによって、検索する方法である。
「2分探索法は、整列されたデータの中央の値と対象データを比較」なので、2で割って中央値を求めます。
したがって、イ)(x+y)/2→mが正解である。