猜數字遊戲：從 1 到 n 中猜一個數字。每次猜測後呼叫
guess(num)API，回傳-1（猜太大）、1（猜太小）或0（猜對了）。找出被選中的數字。
Example:
Input: n = 10, pick = 6 Output: 6
Intuition
TIP
在 [1, n] 區間上做標準二分搜尋，根據 API 回傳值縮小範圍。
- 搜尋空間為 [1, n]，每次猜中間值
- 根據
guess()的回傳值決定往左還是往右
Approaches
1. Linear Scan — O(n) / O(1)
- Idea: 從 1 到 n 逐一猜測
- Time:
O(n) - Space:
O(1)
Linear Scan Code
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 — O(log n) / O(1)
- Idea: 在 [1, n] 上二分搜尋，利用
guess()API 判斷方向 - Time:
O(log n) - Space:
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: 標準二分搜尋（互動式）
- Key trick: 注意
guess()API 的回傳值定義，-1表示你猜的數太大（不是目標比較小），容易搞混方向