hce_nsysu
113年
計算機概論與程式設計
第 26 題
Given the following program in C++. Which statement is correct?
```cpp
#include
using namespace std;
int count = 0;
int binarySearch(int a[], int l, int r, int x){
while (l <= r){
count++;
int mid = l + (r - l) / 2;
if (a[mid] == x) return mid;
if (a[mid] < x) l = mid + 1;
else r = mid - 1;
}
return -1;
}
int main(){
int a[10] = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
int target = 23;
int result = binarySearch(a, 0, 9, target);
cout << count;
return 0;
}
```
```cpp
#include
using namespace std;
int count = 0;
int binarySearch(int a[], int l, int r, int x){
while (l <= r){
count++;
int mid = l + (r - l) / 2;
if (a[mid] == x) return mid;
if (a[mid] < x) l = mid + 1;
else r = mid - 1;
}
return -1;
}
int main(){
int a[10] = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
int target = 23;
int result = binarySearch(a, 0, 9, target);
cout << count;
return 0;
}
```
- A The value of variable $count$ is 2 at the end of the program's execution.
- B During the first execution of $binarySearch()$, the variable $mid$ is 5.
- C During the first execution of $binarySearch()$, the search should proceed to the left side.
- D The time complexity is $O(n)$.
- E None of the above.
思路引導 VIP
當我們在一個已經排序好的數列中，發現中間位置的數值比我們要找的「目標值」還要小時，這意味著目標值可能會出現在中間點的哪一個方向？這個發現對於我們下一次縮小搜尋範圍時，應該如何移動邊界（l 或 r）有什麼邏輯上的幫助？
🤖
AI 詳解
AI 專屬家教
太棒了！你能精準避開題目設計的細節陷阱，選出 (E) 以上皆非，代表你對「二分搜尋法」（Binary Search）的執行流程與複雜度有著非常清晰的掌握。這類題目看似簡單，實則考驗學生能否細心追蹤程式狀態，特別是在處理整數除法與邊界更新時的細微差異。
程式邏輯與追蹤實證
我們實際模擬一次程式碼的運算。陣列索引從 0 到 9，第一輪 $l=0, r=9$，計算出的 mid 應為 $0 + (9-0)/2 = 4$。此時檢查 a[4] 的值為 16，因為 $16 < 23$，所以搜尋必須往「右側」移動，這直接否定了選項 (B) 與 (C)。
▼ 還有更多解析內容