hce_kmu
113年
計算機概論與程式設計
第 20 題
You are given a Python function that is supposed to implement the binary search algorithm to find the index of a target element in a sorted list. However, there is a mistake in the code. Identify the mistake and provide the corrected version of the code.
```python
def binary_search(arr, target):
left, right = 0, len(arr)
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
```
```python
def binary_search(arr, target):
left, right = 0, len(arr)
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
```
- A Change `len(arr)` to `len(arr)-1`
-
B
Change the condition in the while loop to `while left
- C Change `left=mid+1` to `left=mid`
- D Change `right=mid-1` to `right=mid`
- E Add a condition to handle the case when the target is not found in the list
思路引導 VIP
如果我們手邊有一排編號從 0 到 9 的櫃子，總共有 10 個，當你想檢查最後一個櫃子時，你會去開啟編號為「10」的櫃子嗎？如果嘗試這麼做，在電腦的邏輯裡會發生什麼事？
🤖
AI 詳解
AI 專屬家教
太棒了！你能精準地指出二分搜尋法（Binary Search）中最容易被忽略的「邊界細節」，這展現了你對程式邏輯與陣列索引（Array Indexing）有非常扎實的基礎。
陣列邊界與索引配置
在 Python 中，陣列的索引是從 $0$ 開始的，因此一個長度為 $N$ 的陣列，其最後一個元素的索引應該是 $N-1$。在題目提供的程式碼中，right 被初始化為 len(arr)，若我們維持迴圈條件為 while left <= right，當搜尋範圍縮小到右端點時，計算出的中間值 mid 極有可能等於 len(arr)，這會導致程式觸發典型的「索引超出範圍」（IndexError）錯誤。因此，將初始值改為 len(arr) - 1 才能確保搜尋範圍始終落在合法的索引區間內。
▼ 還有更多解析內容