問題プレビューID: 4a70dee1応用情報技術者試験 2011年(平成23年度)秋期 午前

問 8
応用情報技術者試験 2011年(平成23年度)秋期 午前

データが昇順にソートされた配列 X[i]X[i](i=0,1,…,n−1i = 0, 1, \ldots, n-1)を 2 分探索する。流れ図の a に入るものとして,適切なものはどれか。ここで,流れ図の中の割り算は小数点以下を切り捨てるものとする。

〔流れ図〕

開始
 ↓
in に探索値を入力
 ↓
sch ← −1
left ← 0
right ← n − 1
 ↓
ループ1:(sch = −1) and ( a ) を満たす間,繰り返す
 ↓
center ← (left + right) ÷ 2
 ↓
X[center] と in を比較
   X[center] < in  → left ← center + 1
   X[center] = in  → sch ← center
   X[center] > in  → right ← center − 1
 ↓
ループ1 の先頭に戻る
 ↓
sch を表示
 ↓
終了
解説

正解は「イ」です。

2 分探索では,探索範囲を [left,right][left, right] とし,その範囲の中間要素 X[center]X[center] と探索値を比較して,探索範囲を左半分又は右半分に絞り込みます。範囲に要素が存在する限り探索を続け,範囲が空になった時点で探索を終了します。

探索範囲に要素が存在する条件は left≤rightleft \leq right です。left>rightleft > right になると探索範囲は空であり,探索を続ける意味がないためループを終了します。したがって,空欄 a には left≤rightleft \leq right が入ります。

  • ア: left<rightleft < right では,探索範囲が 1 要素(left=rightleft = right)のときにその要素を調べずに終了してしまいます。
  • ウ・エ: left+1left + 1 と比較する条件は探索範囲の判定として適切ではありません。

よって,正解は「イ」です。

関連問題

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