프로그래밍의 기초(의사 코드 트레이스)
÷는 나눗셈이며, 정수형 변수(인수 포함)에 대입할 때는 소수점 이하를 버린다. 다음 프로그램은 오름차순으로 정렬된 정수형 배열 data(인덱스는 1부터 시작)에서 x 이상인 값이 처음 나타나는 인덱스를 lo에 구한다. x는 data의 마지막 요소 이하라고 한다. 프로그램 중의 【a】에 들어갈 것은?
integer: lo ← 1, hi ← length(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이면 범위가 좁아지지 않아 반복이 끝나지 않습니다.