374. 猜数字大小 Easy

我们正在玩猜数字游戏。猜数字游戏的规则如下：

我会从 1 到 n 随机选择一个数字。 请你猜选出的是哪个数字。

如果你猜错了，我会告诉你，我选出的数字比你猜测的数字大了还是小了。

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

• -1：你猜的数字比我选出的数字大 （即 num > pick）。
• 1：你猜的数字比我选出的数字小 （即 num < pick）。
• 0：你猜的数字与我选出的数字相等。（即 num == pick）。

返回我选出的数字。

示例 1:
输入：n = 10, pick = 6
输出：6

示例 2:
输入：n = 1, pick = 1
输出：1

示例 3:
输入：n = 2, pick = 1
输出：1

解题思路

输入： 一个数字 n，一个预定函数 guess

输出： 返回选出的数字

本题属于基础查找类问题，适用于使用二分查找在有序数组中快速定位目标值。

通过二分找到 [0, n] 的中位数去用 guess 判断是在选出的数字左侧还是右侧

guess 返回 0 则选对了

guess 返回 1 则说明中位数在左侧，收缩右边界

guess 返回 1 则说明中位数在右侧，收缩左边界

代码实现

python

class Solution:
    def guessNumber(self, n: int) -> int:
        # 定义二分查找的左右边界
        l, h = 0, n

        # 当左边界 <= 右边界时，继续查找
        while l <= h:
            # 取中点
            mid = (l + h) // 2

            # 调用 API guess(mid)
            # guess(mid) == 0 表示猜中了
            if guess(mid) == 0:
                return mid
            
            # guess(mid) == 1 表示目标数比 mid 大，应该往右边找
            if guess(mid) == 1:
                l = mid + 1
            else:
                # 否则（guess(mid) == -1），目标数比 mid 小，往左边找
                h = mid - 1

javascript

/**
 * @param {number} n
 * @return {number}
 */
var guessNumber = function(n) {
    let low = 0;
    let high = n;

    while (low <= high) {
        const mid = Math.floor((low + high) / 2);

        if (guess(mid) === 0) return mid;

        if (guess(mid) === 1) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
};

复杂度分析

时间复杂度：O(log n)

空间复杂度：O(1)

链接

374 国际版

374 中文版