程式設計基礎（虛擬碼追蹤）
÷ 為除法，代入整數型變數（含引數）時捨去小數部分。下列程式在以遞增順序排好的整數型陣列 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 排除在範圍外，使範圍確實縮小。