LeetCode 374. 猜数字大小
题目描述
题意分析
系统在
[1,n]中固定选择一个目标，每次调用guess(num)只得到它与猜测值的大小关系，需要据此找出目标。返回
-1表示猜大了，目标小于num；返回1表示猜小了，目标大于num；返回0才表示命中。反馈方向必须以“目标相对当前猜测的位置”理解。
解法：二分猜数
核心思路
[!blue]
候选值本来就是连续有序整数，不需要逐个试探。用闭区间
[left,right]保存尚未排除的候选，并始终保证目标在其中；查询中点能够一次确定目标位于哪一半。若反馈为零，直接返回
mid。若为负，目标严格小于中点，mid及其右侧都可以排除，令right = mid-1；若为正，目标严格大于中点，令left = mid+1。这里已经单独处理了命中情况，因此两个未命中分支都不需要保留中点。每次更新既保留了真正目标，又严格缩小候选范围。题目保证目标存在，正确反馈不会把全部候选排空。当左右边界相等时，只剩下的这个整数必然是目标，可以直接返回，不必为它再调用一次接口。
每轮把
guess(mid)的结果存下来再分支，避免同一次判断重复查询。中点使用left + (right-left)/2，即使n接近 32 位整数上限，也不会因直接相加而溢出。
解题步骤
- 初始化
left = 1、right = n，两个端点都属于合法猜测范围。- 当
left < right时计算中点，调用一次guess(mid)并保存反馈。- 命中就返回；否则按反馈排除中点及不含目标的那一侧。
- 循环结束后返回
left。当n == 1时，初始区间已经唯一，无需查询。
代码实现
public class Solution extends GuessGame {
public int guessNumber(int n) {
int left = 1;
int right = n;
while (left < right) {
int mid = left + (right - left) / 2;
// 每轮只调用一次接口，保存反馈后再分支。
int result = guess(mid);
if (result == 0) {
return mid;
}
// 负反馈表示目标更小，排除中点和右侧区间。
if (result < 0) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return left;
}
}
func guessNumber(n int) int {
left, right := 1, n
for left < right {
mid := left + (right-left)/2
// 每轮只调用一次接口，保存反馈后再分支。
result := guess(mid)
if result == 0 {
return mid
}
// 负反馈表示目标更小，排除中点和右侧区间。
if result < 0 {
right = mid - 1
} else {
left = mid + 1
}
}
return left
}
复杂度分析
- 时间复杂度：$O(\log(n+1))$，每轮排除约一半候选。
- 空间复杂度：$O(1)$。
关键点总结
[!green]
- 返回负数表示目标更小，需要缩小右边界。
- 未命中时中点可以排除，使用 mid±1。
- 每轮只调用一次接口并复用结果。
易错点总结
[!yellow]
- 记反反馈方向：把目标所在半区排除。
- 使用 left=mid 配合向下取整：两个候选时可能不再推进。
- 右端初值为 n-1：漏掉目标恰好为 n 的情况。
- 直接相加计算中点：大范围时可能溢出。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 278. 第一个错误的版本 | 简单 | 都通过外部判定接口二分，本题每次得到偏大或偏小，原题找真假分界点。 |
| 704. 二分查找 | 简单 | 比较结果由guess接口提供，更新左右边界的逻辑与有序数组二分相同。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！