374. Guess Number Higher Or Lower

Easy

Description

猜數字遊戲：從 1 到 n 中猜一個數字。每次猜測後呼叫 guess(num) API，回傳 -1（猜太大）、1（猜太小）或 0（猜對了）。找出被選中的數字。

Example:

Input: n = 10, pick = 6 Output: 6

Intuition#

在 [1, n] 區間上做標準二分搜尋，根據 API 回傳值縮小範圍。

搜尋空間為 [1, n]，每次猜中間值
根據 guess() 的回傳值決定往左還是往右

Approaches#

1: Linear Scan#

概念: 從 1 到 n 逐一猜測
時間複雜度: O(n)
空間複雜度: O(1)

Linear Scan 程式碼

class Solution : GuessGame() {
    override fun guessNumber(n: Int): Int {
        for (i in 1..n) {
            if (guess(i) == 0) return i
        }
        return n
    }
}

⭐2: Binary Search#

概念: 在 [1, n] 上二分搜尋，利用 guess() API 判斷方向
時間複雜度: O(log n)
空間複雜度: O(1)

class Solution : GuessGame() {
    override fun guessNumber(n: Int): Int {
        var left = 1
        var right = n
        while (left <= right) {
            val mid = left + (right - left) / 2
            when (guess(mid)) {
                0 -> return mid
                -1 -> right = mid - 1  // 猜太大
                1 -> left = mid + 1     // 猜太小
            }
        }
        return -1
    }
}

🔑 Takeaways#

Pattern: 標準二分搜尋（互動式）
關鍵技巧: 注意 guess() API 的回傳值定義，-1 表示你猜的數太大（不是目標比較小），容易搞混方向