猜数字大小

难度:

标签:

题目描述

猜数字游戏的规则如下：

每轮游戏，我都会从 1 到 n 随机选择一个数字。请你猜选出的是哪个数字。
如果你猜错了，我会告诉你，你猜测的数字比我选出的数字是大了还是小了。

你可以通过调用一个预先定义好的接口 int guess(int num) 来获取猜测结果，返回值一共有 3 种可能的情况（-1，1 或 0）：

-1：我选出的数字比你猜的数字小 pick < num
1：我选出的数字比你猜的数字大 pick > num
0：我选出的数字和你猜的数字一样。恭喜！你猜对了！pick == num

返回我选出的数字。

示例 1：

输入：n = 10, pick = 6
输出：6

示例 2：

输入：n = 1, pick = 1
输出：1

示例 3：

输入：n = 2, pick = 1
输出：1

示例 4：

输入：n = 2, pick = 2
输出：2

提示：

1 <= n <= 2³¹ - 1
1 <= pick <= n

代码结果

运行时间: 17 ms, 内存: 15.9 MB

/*
  思路：使用Java Stream API不太适合这种需要修改边界值的逻辑问题。我们依然使用二分查找的思路来解决问题，但是为了演示Stream的用法，
  这里将Stream用于猜测值的生成过程。
*/
import java.util.stream.IntStream;
 
public class Solution extends GuessGame {
    public int guessNumber(int n) {
        int left = 1, right = n;
        while (left <= right) {
            int mid = IntStream.range(left, right + 1).reduce((a, b) -> a + (b - a) / 2).getAsInt();
            int res = guess(mid);
            if (res == 0) {
                return mid; // 找到pick
            } else if (res < 0) {
                right = mid - 1; // pick在左边
            } else {
                left = mid + 1; // pick在右边
            }
        }
        return -1; // 错误情况，理论上不会到达这里
    }
}

解释

方法:

这道题使用二分查找的思路来猜数字。每次根据 guess 函数的返回值，缩小搜索范围，直到找到目标数字。如果 guess 返回 -1，说明猜的数字偏大，缩小右边界；如果返回 1，说明猜的数字偏小，缩小左边界；如果返回 0，说明猜中了，直接返回当前数字。

时间复杂度:

O(log n)

空间复杂度:

O(1)

代码细节讲解

🦆

在二分查找中，如果猜测的数字和目标数字相等时，为什么是直接返回当前的中间值 mid？

▷

在二分查找中，目标是找到一个特定的数字。当 guess 函数返回 0 时，这表示猜测的数字 mid 等于目标数字。因此，mid 是我们要找的准确数字，直接返回 mid 是因为已经确切地找到了所需的结果，无需进一步搜索。

🦆

在二分查找的过程中，如何确保不会错过目标数字，特别是当区间缩小到只剩两个或三个数字时？

▷

二分查找通过每次将搜索范围减半来确保不会错过目标数字。当区间仅剩两个或三个数字时，算法逐步检查每个可能的位置（通过设置新的 left 或 right 边界），直到找到目标数字或区间缩小到一个元素。通过这种方法，即使区间很小，也能确保不会错过目标数字。

🦆

对于变量 mid 的计算方式 'mid = (left + right) // 2'，是否存在整型溢出的风险，尤其是当 n 非常大时？

▷

在某些编程语言中，直接使用 'left + right' 可能会在 left 和 right 都非常大时引起整数溢出。在 Python 中，整数类型支持大整数运算，因此理论上不会遇到这种溢出问题。但在其他一些语言中，如 Java 或 C++，建议使用 'left + (right - left) / 2' 来避免溢出。

🦆

当 guess(mid) 返回 -1 或 1 时，为何选择修改边界值为 'mid - 1' 或 'mid + 1' 而不是仅仅是 'mid'？

▷

当 guess(mid) 返回 -1 时，表示猜的数字大于目标数字，因此需要排除 mid 及其右边的所有数字，所以将 right 设置为 mid - 1。相反，当返回 1 时，表示猜的数字小于目标数字，需要排除 mid 及其左边的数字，因此将 left 设置为 mid + 1。这样的调整保证了每次都缩小搜索范围，有效地逼近目标数字。

相关问题

第一个错误的版本

你是产品经理，目前正在带领一个团队开发新的产品。不幸的是，你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的。

假设你有 n 个版本 [1, 2, ..., n]，你想找出导致之后所有版本出错的第一个错误的版本。

你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。

示例 1：

输入：n = 5, bad = 4
输出：4
解释：
调用 isBadVersion(3) -> false 
调用 isBadVersion(5) -> true 
调用 isBadVersion(4) -> true
所以，4 是第一个错误的版本。

示例 2：

输入：n = 1, bad = 1
输出：1

提示：

1 <= bad <= n <= 2³¹ - 1