プログラミングの基礎(擬似言語のトレース)
÷ は除算で、整数型の変数(引数を含む)に代入するときは小数点以下を切り捨てる。次のプログラムは、昇順に整列された整数型の配列 data(要素番号は1から始まる)で、x 以上の値が最初に現れる要素番号を lo に求める。x は data の最後の要素以下とする。プログラム中の【a】に入れる字句はどれか。
整数型: lo ← 1, hi ← dataの要素数, mid
while (lo < hi)
mid ← (lo + hi) ÷ 2
if (data[mid] < x)
lo ← 【a】
else
hi ← mid
endif
endwhile- Amid
- Bmid − 1
- Cmid + 1
答えと解説を見る
正解：C. mid + 1
data[mid] < x なら、data[mid] とそれより前の要素はすべて x 未満なので、答えは mid + 1 以降にあります。そうでなければ data[mid] ≧ x で、答えは mid 以前にあるので hi ← mid とします。lo ← mid + 1 なら範囲は毎回確実に狭まり、lo = hi になったところが答えです。lo ← mid にすると、lo と hi が隣り合ったときに mid = lo となり、data[mid] < x なら範囲が狭まらずに繰返しが終わりません。
- A. lo と hi が隣り合い data[lo] < x のとき、mid = lo のまま範囲が狭まらず、繰返しが終わりません。例えば data = {3, 8, 12, 17, 23, 31}、x = 31 では lo = 5、hi = 6 のまま止まりません。
- B. 答えより手前に lo を戻してしまい、範囲が狭まらないことがあります。data = {3, 8, 12, 17, 23, 31}、x = 4 では lo が0になり、繰返しが終わりません。
- C. 正しい。x 未満と分かった mid を範囲から除き、範囲を確実に狭めます。