网络异常，图片无法展示
|
题目描述
这是 LeetCode 上的 374. 猜数字大小 ，难度为 简单。
Tag : 「二分」
猜数字游戏的规则如下：
- 每轮游戏，我都会从 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^{31}231 - 1
- 1 <= pick <= n
二分
端午安康呀 🍭🍭🍭
今天的题目表达不太好 🤣，还是逐字阅读才明白是啥意思 🤣
就当做是因为题目本身要比 278. 第一个错误的版本 简单（不需要考虑完全相同，没有二段性的情况），所以在阅读上增加了难度吧 🤣
一道交互题，根据题意可知，是尽可能少调用 guess 方法来找到分割点。
直接使用 guess 当做 check 函数进行二分即可。
另外根据数据范围需要注意计算 mid 时的爆 int 问题，可以通过使用类似 l + (r - l) / 2 的做法解决，也可以通过一个临时 long 来解决。
代码：
public class Solution extends GuessGame { public int guessNumber(int n) { int l = 1, r = n; while (l < r) { long tmp = (long)l + r>> 1; int mid = (int)tmp; if (guess(mid) <= 0) { r = mid; } else { l = mid + 1; } } return r; } } 复制代码
public class Solution extends GuessGame { public int guessNumber(int n) { int l = 1, r = n; while (l < r) { long tmp = (long)l + r + 1 >> 1; int mid = (int)tmp; if (guess(mid) >= 0) { l = mid; } else { r = mid - 1; } } return r; } } 复制代码
- 时间复杂度：O(\log{n})O(logn)
- 空间复杂度：O(1)O(1)
其他「二分」相关题解
- 二分模板 29. 两数相除 : 二分 + 倍增乘法解法（含模板）
- 二分模板题 278. 第一个错误的版本 : 使用交互函数充当 check 进行二分
374. 猜数字大小 : 使用交互函数充当 check 进行二分 - 二分本质 & 恢复二段性处理
33. 搜索旋转排序数组（找目标值） : 严格 O(logN)，一起看清二分的本质
81. 搜索旋转排序数组 II（找目标值） : 详解为何元素相同会导致 O(n)，一起看清二分的本质
153. 寻找旋转排序数组中的最小值（找最小值） : 严格 O(logN)，一起看清二分的本质
154. 寻找旋转排序数组中的最小值 II（找最小值） : 详解为何元素相同会导致 O(n)，一起看清二分的本质 - 二分 check 函数如何确定 34. 在排序数组中查找元素的第一个和最后一个位置 : 考察对「二分」的理解，以及 check 函数的「大于 小于」怎么写
最后
这是我们「刷穿 LeetCode」系列文章的第 No.374 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先将所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：github.com/SharingSour… 。
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
