猜数字大小 图解题解

只靠偏大偏小的回复，怎么锁定 pick

系统在 1 到 n 里偷偷选了一个数 pick。你能做的只有一件事：挑一个数 m 去问 guess(m)，它回 1 表示 m 比 pick 小（猜小了）、回 −1 表示 m 比 pick 大（猜大了）、回 0 表示命中。看不到答案、只能靠每次回复一点点逼近，这种方式叫交互反馈。题目要的不是随便猜中，而是用尽量少的次数问出 pick。

从 1 开始一个个问，为什么会被卡死

笨办法是从 1 挨个问：guess(1)、guess(2)、guess(3)……直到返回 0。一定能中，可 pick 若靠近 n 就得问将近 n 次，n 到十亿这条线性扫（从头一个个试）就慢得没法接受。更亏的是，guess 明明告诉了你「偏大还是偏小」，挨个问却只用「中没中」，方向信息全浪费。

偏大偏小这条回复，凭什么能砍掉一半

关键在于 1 到 n 本身从小到大排好。挑正中间的数 m 去问，guess 的回复直接圈定 pick 在哪半边：回 1 说明 pick 比 m 大，m 连同左边整段排除；回 −1 说明 pick 比 m 小，m 连同右边全排除。一问就砍掉一半候选，这正是二分查找（每问一次，候选就减半的找法）能用的前提。

区间怎么收、mid 怎么取才不会漏掉 pick

用 lo、hi 两头框住还没排除的候选，起初 lo=1、hi=n，闭区间 [lo, hi]（两端都算数）里自始至终含着 pick。每轮取中点 mid = lo + (hi − lo) // 2，问 guess(mid)：回 0 就返回 mid；回 1 说明 pick 更大，lo = mid + 1；回 −1 说明 pick 更小，hi = mid − 1。收缩必须 ±1——mid 已问过、不是答案，得跨过它，否则区间缩不动、一直空转。lo 超过 hi 时候选空了，循环停。

拿 n=10、pick=6 逐轮把区间夹到底

拿题面的 n=10、pick=6 走一遍。第一轮 lo=1、hi=10，mid = 1 + (10 − 1) // 2 = 5，guess(5) 返回 1（5 比 6 小），pick 在右半，lo 提到 6。第二轮 lo=6、hi=10，mid = 6 + (10 − 6) // 2 = 8，guess(8) 返回 −1（8 比 6 大），pick 在左半，hi 退到 7。第三轮 lo=6、hi=7，mid = 6 + (7 − 6) // 2 = 6，guess(6) 返回 0，命中返回 6。十个数只问 3 次就锁定，每轮都砍掉一半。

认反 guess 的方向，越问越偏

每问一次候选减半，最多约 log₂n 次收敛，时间 O(log n)；只用 lo、hi、mid 三个记号，空间 O(1)。最坑是 guess 方向记反：返回 1 是猜小了、该 lo = mid + 1，反着写越问越偏。收缩漏 ±1、写成 lo = mid，mid 不挪、循环卡死。mid 写 (lo+hi)//2 在 n 大时溢出，换 lo + (hi − lo) // 2 才稳；n=1 一问即中，两端值也照常收敛。

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 -1

C++

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;
    }
}