374. Guess Number Higher or Lower

📘 題目敘述

我們正在玩「猜數字」遊戲，規則如下：

我會從 1 到 n 選一個數字。你要猜我選的是哪一個數字（我選的數字在整個遊戲過程中都不會改變）。

每次你猜錯時，我會告訴你我選的數字是比你的猜測「更大」或「更小」。

你可以呼叫一個已經定義好的 API：int guess(int num)，它會回傳三種結果：

• -1：你的猜測比我選的數字大，也就是 num > pick
• 1：你的猜測比我選的數字小，也就是 num < pick
• 0：你的猜測等於我選的數字，也就是 num == pick

請回傳我選的那個數字。

條件限制

• 1 <= n <= 2^31 - 1
• 1 <= pick <= n

🧠 解題思路

這題我直接用二分搜尋，因為題目本質就是「在 1 到 n 的範圍內找一個固定答案」，而且 guess(mid) 會告訴我答案在左半邊還是右半邊。

我維持一個搜尋區間 [l, r]：

• 如果 guess(mid) == -1，代表我猜太大，答案一定在左邊，所以縮到左半邊
• 如果 guess(mid) == 1，代表我猜太小，答案一定在右半邊，所以縮到右半邊
• 如果 guess(mid) == 0，代表猜中，直接回傳

另外我用 mid = l + (r - l) / 2，避免 (l + r) / 2 在 n 很大時可能溢位。

所有變數

• l：目前二分搜尋區間的左界
• r：目前二分搜尋區間的右界
• mid：目前猜的中間值
• ans：guess(mid) 的回傳結果（-1 / 1 / 0）

🪜 主要流程步驟

1. 初始化搜尋範圍

把答案可能出現的範圍設成 [1, n]，也就是 l = 1, r = n。

2. 每次取中間值去猜

在 l < r 的情況下不斷迴圈，計算：

mid = l + (r - l) / 2

然後呼叫 guess(mid) 取得結果。

3. 用 guess 的結果縮小範圍

• ans == -1：我猜太大，答案在左邊，所以把 r 改成 mid - 1
• ans == 1：我猜太小，答案在右邊，所以把 l 改成 mid + 1
• ans == 0：猜中，直接回傳 mid

4. 迴圈結束時回傳 l

當 l == r 時，代表範圍已經縮成只剩一個數字，答案就是 l。

⏱️ 複雜度

• 時間複雜度：O(log n)（每次把範圍砍半）
• 空間複雜度：O(1)

💻 程式碼實作

/**
 * Forward declaration of guess API.
 * @param  num   your guess
 * @return       -1 if num is higher than the picked number
 *                1 if num is lower than the picked number
 *               otherwise return 0
 * int guess(int num);
 */

class Solution {
public:
    int guessNumber(int n) {
        int l = 1, r = n;
        int mid;
        while (l < r) {
            mid = l + (r - l) / 2;  //(l+r)/2會超過int
            int ans = guess(mid);
            if (ans == -1) {
                r = mid - 1;
            } else if (ans == 1) {
                l = mid + 1;
            } else {
                return mid;
            }
        }
        return l;
    }
};

🔗 題目連結

https://leetcode.com/problems/guess-number-higher-or-lower/