hce_kmu
114年
計算機概論與程式設計
第 21 題
Consider the following binary search program written in Python. Please select the CORRECT statement when the input array arr contains exactly 10 numbers.
```python
def binary_search(arr, key):
low, high = 0, len(arr) - 1
while low <= high:
center = (low + high) // 2
if arr[center] == key:
return center
elif key < arr[center]:
high = center - 1
else:
low = center + 1
return -1
```
```python
def binary_search(arr, key):
low, high = 0, len(arr) - 1
while low <= high:
center = (low + high) // 2
if arr[center] == key:
return center
elif key < arr[center]:
high = center - 1
else:
low = center + 1
return -1
```
- A When all the numbers in arr are the same, it will return 0.
- B When the key is greater than max(arr), it will return 10.
- C When the key is greater than max(arr), it will return 11.
- D It is applicable to a monotonically increasing sequence.
- E If you forget to sort arr first, it will return -1 regardless of the key.
思路引導 VIP
如果你在一本完全沒有按照字母順序排列的電話簿中，試圖用「翻開中間那一頁」的方法來縮小尋找範圍，你覺得這個方法還會有效嗎？為什麼「有序排列」對於這種快速尋找的策略如此重要？
🤖
AI 詳解
AI 專屬家教
太棒了！你能精確辨識出二元搜尋（Binary Search）的核心前提，代表你對演算法的基礎觀念掌握得非常紮實。這題選 (D) 是完全正確的，因為二元搜尋的邏輯建立在「排除一半可能性」的基礎上。當我們檢查中間值 $\text{arr[center]}$ 時，必須確保序列是**單調遞增（Monotonically Increasing）**或遞減的，這樣才能根據大小關係判斷目標值位在左半部還是右半部。若數列無序，這種「減而治之」的策略就會失效。
演算法的前提與限制
關於其他選項的陷阱，我們可以簡單釐清：當輸入陣列未經排序時，程式不一定會回傳 -1，而是會產生不可預測的錯誤結果（隨機剛好對到中點仍可能回傳）。而當搜尋值大於最大值時，依程式邏輯最終會因 low > high 離開迴圈並回傳 -1，而非回傳索引值。這題的鑑別度在於它不要求你死背程式碼的每一行，而是考驗你是否理解二元搜尋的「必要條件」。對於剛接觸演算法的同學來說，區分「能跑出結果」與「邏輯正確」是進階到中階開發者的關鍵切入點。