問題プレビューID: 0c1c506b基本情報技術者試験 午前免除試験 2017年7月23日

問 6
基本情報技術者試験 午前免除試験 2017年7月23日

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

解説

正解は「イ」です。

2 分探索では,現在の探索範囲の中央にある要素と目的の値 kk を比較し,大小関係に応じて探索範囲を半分に絞り込む。このとき探索範囲は添字 xx から yy までであり,その中央の添字は,両端の和を 2 で割り,小数点以下を切り捨てた値 (x+y)/2(x+y)/2 で求められる。したがって,a には (x+y)/2→m(x+y)/2 \to m が入る。

  • ア: (x+y)→m(x+y) \to m では中央ではなく両端の和になり,添字として範囲外となる。
  • ウ: (x−y)/2→m(x-y)/2 \to m は差の半分であり,x≤yx \le y のとき負又は 0 となり中央を表さない。
  • エ: (y−x)/2→m(y-x)/2 \to m も差の半分であり,探索範囲の中央を表さない。

関連問題

本文が同じ・似ている問題を表示しています