374. 猜数字大小
题目描述
系统事先从 1 到 n 中选定一个整数 pick，整个过程中它不会变。你的任务是找出这个数。
可以调用现成的接口 guess(num) 来试探。它返回 -1 表示猜大了（num > pick）；返回 1 表示猜小了（num < pick）；返回 0 表示猜对了。
函数只接收 n，返回 pick 的值。示例中给出的 pick 只用于说明答案。
示例 1
输入：n = 10, pick = 6 输出：6
示例 2
输入：n = 1, pick = 1 输出：1
解释：只有一个候选数 1。
示例 3
输入：n = 2, pick = 1 输出：1
数据范围
1 <= n <= 2^31 - 11 <= pick <= n
解题思路
经典闭区间二分。候选区间 [lo, hi] 一开始是 [1, n]。每次猜中点 mid：返回 0 就是答案；返回 1 说明 pick 比 mid 大，lo = mid + 1；返回 -1 说明 pick 比 mid 小，hi = mid - 1。
为什么正确
pick 始终在 [lo, hi] 中。
复杂度分析
至多调用 guess 约 log2(n) + 1 次，时间 O(log n)，空间 O(1)。
易错点
返回值的含义容易弄反：-1 是“你猜的数太大”，要往左找。另外 n 可达 2^31 - 1，(lo + hi) 在 32 位整数中会溢出，要写 lo + (hi - lo) // 2。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def guessNumber(self, n: int) -> int:
lo, hi = 1, n
while lo <= hi:
mid = lo + (hi - lo) // 2
res = guess(mid)
if res == 0:
return mid
if res == 1:
lo = mid + 1
else:
hi = mid - 1
return -1class Solution extends GuessGame {
public int guessNumber(int n) {
int lo = 1, hi = n;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
int res = guess(mid);
if (res == 0) {
return mid;
}
if (res == 1) {
lo = mid + 1;
} else {
hi = mid - 1;
}
}
return -1;
}
}class Solution {
public:
int guessNumber(int n) {
int lo = 1, hi = n;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
int res = guess(mid);
if (res == 0) {
return mid;
}
if (res == 1) {
lo = mid + 1;
} else {
hi = mid - 1;
}
}
return -1;
}
};func guessNumber(n int) int {
lo, hi := 1, n
for lo <= hi {
mid := lo + (hi-lo)/2
res := guess(mid)
if res == 0 {
return mid
}
if res == 1 {
lo = mid + 1
} else {
hi = mid - 1
}
}
return -1
}var guessNumber = function(n) {
let lo = 1, hi = n;
while (lo <= hi) {
const mid = lo + Math.floor((hi - lo) / 2);
const res = guess(mid);
if (res === 0) {
return mid;
}
if (res === 1) {
lo = mid + 1;
} else {
hi = mid - 1;
}
}
return -1;
};function guessNumber(n: number): number {
let lo = 1, hi = n;
while (lo <= hi) {
const mid = lo + Math.floor((hi - lo) / 2);
const res = guess(mid);
if (res === 0) {
return mid;
}
if (res === 1) {
lo = mid + 1;
} else {
hi = mid - 1;
}
}
return -1;
}