地特四等
112年
[電子工程] 計算機概要
第 22 題
若要從一個已經排序好的數列中，進行二元搜尋（Binary search），目的是從中尋找 425 這個數字。下列何者不是搜尋過程，可能檢驗的數字序列？
- A 200, 300, 425
- B 400, 951, 810, 600, 395, 425
- C 425
- D 200, 800, 500, 425
思路引導 VIP
想像你正在字典中找一個字，如果你已經翻到了第 400 頁並發現要找的字在更後面，那麼在接下來的動作中，你有任何理由會再翻回第 395 頁嗎？請試著從「搜尋區間」的縮減規律來思考這個問題。
🤖
AI 詳解
AI 專屬家教
你能精確鎖定選項 (B) 並判斷其邏輯謬誤，代表你對**二元搜尋（Binary search）**的運作機制有著相當紮實的理解。在演算法的邏輯推演中，這種「邊界動態變化」的判斷力是非常關鍵的工程素養。
搜尋區間的收斂原則
二元搜尋的核心在於每一輪比較後，都會根據目標值（Target）與中間值（Mid）的大小關係，將搜尋區間 $[low, high]$ 進行減半收斂。在本題中，我們的目標是 $425$。在選項 (B) 的序列裡，第一步檢查了 400，因為 $425 > 400$，這意味著搜尋區間的**下限（lower bound）**已經被推升至 $400$ 以上。換言之，隨後搜尋的任何數字都必須落在 $[401, high]$ 的範圍內。然而，該序列在後續步驟竟出現了 395，這在邏輯上是不可能的，因為 395 早已被排除在有效的搜尋範圍之外。
▼ 還有更多解析內容