LeetCode 374. 猜数字大小

约 5 分钟
文章信息 7 个分类 2 个标签
分类
LeetCode CodeTop 简单 未解决 1-2 华为 LeetCode 75
标签
二分查找 交互
目录

题目描述

✅ 374. 猜数字大小

题意分析

题目目标：系统在 1 到 n 之间选定了一个数 pick，我们只能通过调用 guess(x) 这个接口去试探，接口返回 -1 表示 pick 比 x 小、返回 1 表示 pick 比 x 大、返回 0 表示猜中，要求用尽可能少的调用次数找出 pick。
核心约束：接口不是简单地告诉我们「对不对」，而是告诉我们「往哪边偏」，这个方向信息是全部题眼——每一次调用都能把候选范围整体切掉一半而不是排除一个点。第二个信号是候选集合本身天然有序（1 到 n 的连续整数），有序加上方向反馈，就构成了折半查找成立的两个必要条件。第三个信号是 n 的上界接近 int 的最大值，说明必须考虑中点计算的溢出问题，也说明线性枚举会超时。
边界处理：n 可能等于 1，此时答案只能是 1，循环一次都不该进；pick 可能落在区间的最左端或最右端，收缩逻辑不能把正确答案挤出候选范围；left + right 在 n 接近 $2^{31}-1$ 时会溢出成负数，中点必须换一种算法；必须严格遵守接口的方向语义，把 -1 和 1 的含义记反会让搜索朝反方向跑。

解法：二分猜数

核心思路

guess(x) 不只告诉我们是否命中，还给出目标在 x 的左侧还是右侧。候选集合 [1, n] 有序，反馈具有单调分界，因此应使用二分查找，把昂贵的接口调用降到对数次。

使用闭区间 [left, right]，并采用“收敛到唯一候选”的写法。每轮只在 left < right 时调用一次 guess(mid)；若接口返回负数，目标严格小于 mid，令 right = mid - 1；若返回正数，令 left = mid + 1；返回 0 则直接结束。

不变量：每轮开始时，系统选择的数字始终位于 [left, right]。接口反馈会排除 mid 以及错误方向的整段区间，所以更新后不变量仍成立，且区间严格缩小。

正确性：显式命中时返回值显然正确；若循环以 left == right 结束，不变量保证唯一剩余候选就是目标。中点写成 left + (right - left) / 2，避免 left + right 在接近 32 位上界时溢出。

解题步骤

  1. 初始化闭区间 [1, n]。
  2. 当区间不止一个候选时，计算安全中点并只调用一次 guess(mid)。
  3. 根据返回值排除中点及一侧区间；命中则立即返回。
  4. 区间收敛后返回 left。

对 n = 10、目标为 6，中点依次可为 5、8、6，接口返回 1、-1、0，最终返回 6。n = 1 时循环不进入，直接返回 1；目标位于 1 或 n 时也不会被错误排除。

代码实现

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)$，每轮排除至少一半候选，并调用一次接口。
  • 空间复杂度：$O(1)$，只使用固定数量的整数变量。

关键点总结

  • 可二分的依据是有序候选与带方向的单调反馈，不要求存在实际数组。
  • guess(mid) 每轮只调用一次，结果保存后复用。
  • 闭区间、循环条件和 mid ± 1 的更新必须配套。
  • 安全中点公式避免大整数相加溢出。

易错点总结

  • 记反接口含义：返回 -1 表示目标更小，应收缩右边界。
  • 中点写成 (left + right) / 2：n 接近 Integer.MAX_VALUE 时可能溢出。
  • 边界从 0 或 n - 1 开始：题目的合法候选是 1 到 n，两端都可能是答案。
  • 更新为 left = mid：向下取整时可能在两个候选间死循环。
  • 重复调用 guess(mid)：交互调用是受限资源，应一次获取并分支处理。

相似题目

题目 难度 考察点
704. 二分查找 简单 同一模板作用在显式有序数组上，判定条件由接口换成元素比较
278. 第一个错误的版本 简单 同为交互式二分，但接口只给布尔值，要找的是分界点而非精确命中
35. 搜索插入位置 简单 目标可能不存在，考察退出后 left 作为插入位置的语义
162. 寻找峰值 中等 数组无序，二分依据变成局部斜率方向，说明单调判定不必来自全局有序
875. 爱吃香蕉的珂珂 中等 在答案空间上二分，判定条件需要自己构造成一个单调的可行性检查
33. 搜索旋转排序数组 中等 有序性被旋转破坏，需要先判断哪半边有序再决定收缩方向