Guess Number Higher or Lower
題目描述
猜一個 1 到 n 的數字，有一個預定義的 API guess(num) 回傳 -1（太高）、1（太低）或 0（正確）。找出正確的數字。
輸入：n = 10, pick = 6
輸出：6
解釋：guess(5) → 1, guess(8) → -1, guess(7) → -1, guess(6) → 0
解題思路
設定範圍
left = 1, right = n，代表答案一定在 [1, n] 之間
取中間值
mid = left + (right - left) / 2，用減法再加法的寫法防止 left + right 超過 int 最大值（約 21 億）
呼叫 API
guess(mid) 回傳三種結果：-1 表示 mid 太高、1 表示 mid 太低、0 表示猜對了
縮小範圍
回傳 -1 → right = mid - 1 淘汰右半；回傳 1 → left = mid + 1 淘汰左半；回傳 0 → 直接 return mid
程式碼
C#
public class Solution : GuessGame {
public int GuessNumber(int n) {
int left = 1, right = n;
while (left <= right) {
int mid = left + (right - left) / 2;
int result = guess(mid);
if (result == 0) return mid;
else if (result == -1) right = mid - 1; // 太高
else left = mid + 1; // 太低
}
return -1; // 不會到這裡
}
}TypeScript
function guessNumber(n: number): number {
let left = 1, right = n;
while (left <= right) {
const mid = Math.floor(left + (right - left) / 2);
const result = guess(mid);
if (result === 0) return mid;
else if (result === -1) right = mid - 1;
else left = mid + 1;
}
return -1;
}Python
def guessNumber(n: int) -> int:
left, right = 1, n
while left <= right:
mid = left + (right - left) // 2
result = guess(mid)
if result == 0:
return mid
elif result == -1: # 猜太高
right = mid - 1
else: # 猜太低
left = mid + 1
return -1複雜度分析
| | Time | Space | |--|------|-------| | 本解法 | O(log n) | O(1) |
- Time：每次迭代將搜尋範圍縮小一半，最多迭代 ceil(log2(n)) 次
- Space：只用了 left、right、mid 三個變數，不隨 n 增長
圖解
流程圖展示了 Binary Search 的決策分支：取中間值後呼叫 API，根據回饋值決定搜尋方向。 每輪淘汰一半範圍，最終收斂到唯一答案。
進階觀點
💡面試追問
Q: 為什麼用 left + (right - left) / 2 而不是 (left + right) / 2？
A: 當 left 和 right 都接近 int 最大值時，兩者相加會超過 2^31 - 1 造成溢位。先做減法再加法可以避免。在 Python 中因為整數無上限所以不受影響。
Q: Binary Search 三種常見變體的差異？
A: 找精確值用 left ≤ right，迴圈內直接 return；找左邊界用 left < right，命中時 right = mid 繼續縮小；找右邊界類似但命中時 left = mid + 1。三者的迴圈條件和收縮方向不同，選錯會導致無窮迴圈或漏解。
Q: 如果 API 有一定機率回傳錯誤結果，如何保證正確性？ A: 可以對同一個 mid 呼叫多次取多數決（如呼叫 11 次取出現 6+ 次的結果），或用機率型二分搜尋。每次多數決的錯誤機率隨呼叫次數指數下降，整體仍為 O(log n) 次猜測。
邊界情況
- n 等於 1：答案一定是 1，迴圈第一次 mid = 1 就會命中 return
- 答案在兩端（pick = 1 或 pick = n）：Binary Search 仍然正確，最多 log n 次就能收斂到邊界
- n 等於 int 最大值（2^31 - 1）：此時
(left + right) / 2會溢位，必須用left + (right - left) / 2的寫法
理解測驗
🤔 為什麼 Binary Search 每次能淘汰一半的搜尋範圍？
🤔 猜 1 到 1000 的數字，最多需要幾次？