374. 猜数字大小
374. 猜数字大小
题目
We are playing the Guess Game. The game is as follows:
I pick a number from 1
to n
. You have to guess which number I picked.
Every time you guess wrong, I will tell you whether the number I picked is higher or lower than your guess.
You call a pre-defined API int guess(int num)
, which returns three possible results:
-1
: Your guess is higher than the number I picked (i.e.num > pick
).1
: Your guess is lower than the number I picked (i.e.num < pick
).0
: your guess is equal to the number I picked (i.e.num == pick
).
Return the number that I picked.
Example 1:
Input: n = 10, pick = 6
Output: 6
Example 2:
Input: n = 1, pick = 1
Output: 1
Example 3:
Input: n = 2, pick = 1
Output: 1
Constraints:
1 <= n <= 2^31 - 1
1 <= pick <= n
题目大意
猜数字游戏的规则如下:
- 每轮游戏,我都会从 1 到 n 随机选择一个数字。 请你猜选出的是哪个数字。
- 如果你猜错了,我会告诉你,你猜测的数字比我选出的数字是大了还是小了。
你可以通过调用一个预先定义好的接口 int guess(int num)
来获取猜测结果,返回值一共有 3 种可能的情况(-1
,1
或 0
):
-1
:我选出的数字比你猜的数字小pick < num
1
:我选出的数字比你猜的数字大pick > num
0
:我选出的数字和你猜的数字一样。恭喜!你猜对了!pick == num
返回我选出的数字。
解题思路
- 初始化搜索范围
left = 1
和right = n
。 - 在每次迭代中,计算中间值
mid = Math.floor((left + right) / 2)
。 - 调用
guess(mid)
:- 如果返回
0
,则找到了目标数字,返回mid
; - 如果返回
1
,说明数字太小,需要在更大的范围中查找,更新left = mid + 1
; - 如果返回
-1
,说明数字太大,需要在更小的范围中查找,更新right = mid - 1
。
- 如果返回
- 循环终止条件为
left > right
,因为题目保证一定存在一个正确答案,所以我们总能在循环内返回结果。
复杂度分析
- 时间复杂度:
O(log n)
,每次将搜索范围缩小一半。 - 空间复杂度:
O(1)
,只使用了常量额外空间。
代码
/**
* @param {number} n
* @return {number}
*/
var guessNumber = function (n) {
let left = 1;
let right = n;
while (left <= right) {
let mid = Math.floor((left + right) / 2); // 计算中间值
let res = guess(mid); // 调用 guess API
if (res === 0) {
return mid; // 猜对了,返回结果
} else if (res === 1) {
left = mid + 1; // 猜小了,移动左边界
} else if (res === -1) {
right = mid - 1; // 猜大了,移动右边界
}
}
};
相关题目
题号 | 标题 | 题解 | 标签 | 难度 | 力扣 |
---|---|---|---|---|---|
278 | 第一个错误的版本 | [✓] | 二分查找 交互 | 🟢 | 🀄️ 🔗 |
375 | 猜数字大小 II | [✓] | 数学 动态规划 博弈 | 🟠 | 🀄️ 🔗 |
658 | 找到 K 个最接近的元素 | [✓] | 数组 双指针 二分查找 3+ | 🟠 | 🀄️ 🔗 |