猜数字大小 图解题解
这道题到底在问什么
- 输入
- n=10, pick=6
- 输出
- 6
最优解：一步一步想明白
- 3记住「取中点 mid → guess → 偏小 lo=mid+1、偏大 hi=mid−1、命中即停」,下面每帧都在套它。
- 4还没被排除的范围是 [1, 12](灰格已排除)。取中点 mid = 6(用整除 (12−1)//2 向下取整:候选个数为奇数时正好是正中间,偶数时取靠左那个),下一步去问 guess(6)。
- 5guess(6) 返回 1。返回 1 表示猜的数比 pick 小,也就是 pick 比 6 大,答案落在它右边。
- 6既然 pick 比 6 大,1 到 6(含刚问过的 6)全部排除、标灰,lo 跳到 7。左半被砍掉,范围缩成 [7, 12]。
- 7还没被排除的范围是 [7, 12](灰格已排除)。取中点 mid = 9(用整除 (12−7)//2 向下取整:候选个数为奇数时正好是正中间,偶数时取靠左那个),下一步去问 guess(9)。
- 8guess(9) 返回 1。返回 1 表示猜的数比 pick 小,也就是 pick 比 9 大,答案落在它右边。
- 9既然 pick 比 9 大,7 到 9(含刚问过的 9)全部排除、标灰,lo 跳到 10。左半被砍掉,范围缩成 [10, 12]。
- 10还没被排除的范围是 [10, 12](灰格已排除)。取中点 mid = 11(用整除 (12−10)//2 向下取整:候选个数为奇数时正好是正中间,偶数时取靠左那个),下一步去问 guess(11)。
- 11guess(11) 返回 -1。返回 −1 表示猜的数比 pick 大,也就是 pick 比 11 小,答案落在它左边。
- 12既然 pick 比 11 小,11 到 12(含刚问过的 11)全部排除、标灰,hi 退到 10。右半被砍掉,范围缩成 [10, 10]。
- 13还没被排除的范围是 [10, 10](灰格已排除)。取中点 mid = 10(用整除 (10−10)//2 向下取整:候选个数为奇数时正好是正中间,偶数时取靠左那个),下一步去问 guess(10)。
- 14guess(10) 返回 0。正好等于 pick,猜中了!
- 1510 就是 pick,绿色标出,二分结束。回头看,从 12 个数里只问了 4 次就锁定了它,每次都砍掉一半,这就是二分的威力。
⚠️ 容易写错的地方
✗ 错：写 mid = (left+right)/2
✓ 对：mid = left + (right−left)//2(整除)
left+right 可能溢出,这种写法等价又安全;中点用整除向下取整
✗ 错：guess 返回值方向搞反
✓ 对：返回 1=猜小了 pick 更大往右、−1=猜大了 pick 更小往左
方向反了会越猜越偏甚至死循环
✗ 错：闭区间忘了 ±1
✓ 对：lo=mid+1 / hi=mid−1
mid 已经问过、必须排除,否则可能死循环
完整代码（Python / C++ / Java）
Python
PICK = 1
def guess(num: int) -> int:
if num == PICK:
return 0
return 1 if num < PICK else -1
class Solution:
def guessNumber(self, n: int) -> int:
left, right = 1, n
while left <= right:
mid = left + (right - left) // 2
g = guess(mid)
if g == 0:
return mid
if g > 0:
left = mid + 1
else:
right = mid - 1
return -1C++
using namespace std;
int PICK = 1;
int guess(int num) {
if (num == PICK) return 0;
return num < PICK ? 1 : -1;
}
class Solution {
public:
int guessNumber(int n) {
int left = 1, right = n;
while (left <= right) {
int mid = left + (right - left) / 2;
int g = guess(mid);
if (g == 0) return mid;
if (g > 0) left = mid + 1;
else right = mid - 1;
}
return -1;
}
};Java
class GuessGame {
static int pick = 1;
int guess(int num) {
if (num == pick) return 0;
return num < pick ? 1 : -1;
}
}
class Solution extends GuessGame {
public int guessNumber(int n) {
int left = 1, right = n;
while (left <= right) {
int mid = left + (right - left) / 2;
int g = guess(mid);
if (g == 0) return mid;
if (g > 0) left = mid + 1;
else right = mid - 1;
}
return -1;
}
}复杂度
时间
O(log n)
每问一次范围减半,最多约 ceil(log2(n+1)) 次就收敛,即 O(log n) 次
空间
O(1)
只用 left、right、mid 几个变量
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 猜数字大小 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
这题和普通「有序数组里二分找值」有什么区别?+
本质一样,都是在有序范围 1..n 上二分。区别只是这里没有现成数组,而是通过 guess(mid) 这个 API 间接知道 mid 和目标的大小关系;比较的不是 nums[mid] 而是 guess 的返回值。把它看成「在 1..n 上对 guess 做二分」就通了。
为什么用闭区间 [left,right]、循环条件 left ≤ right?+
闭区间表示「答案还可能落在 [left,right] 里」。每次 mid 问过就排除,所以 lo=mid+1 或 hi=mid−1;当 left 大于 right 时区间为空、说明已问完。配 left ≤ right 能正确处理到最后只剩一个数的情况。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 猜数字大小 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。