题目:
猜数字游戏的规则如下:
每轮游戏,我都会从 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 - 1
- 1 <= pick <= n
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/guess-number-higher-or-lower
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
解题思路:
【二分查找】
理解题目意思,就是逐渐缩小猜测范围,设定左右指针并初始化,left = 1,right = n,计算出mid的值:mid = left + (right - left) / 2,循环的条件是:left < = right,分情况讨论缩小区间:
- guss(mid)返回的是 -1:代表选出的数字比猜的数字小 pick < mid,就是猜大了,就应该缩小右边界,即right = mid - 1;
- guss(mid)返回的是 1:代表选出的数字比猜的数字大 pick > mid,就是猜小了,就应该缩小左边界,即left = mid + 1;
- guss(mid)返回的是 0:代表选出的数字和猜的数字一样 pick == mid,直接返回mid。
循环结束的条件是:left > right,表示没有找到,直接返回 -1
java代码:
1 /** 2 * Forward declaration of guess API. 3 * @param num your guess 4 * @return -1 if num is higher than the picked number 5 * 1 if num is lower than the picked number 6 * otherwise return 0 7 * int guess(int num); 8 */ 9 10 public class Solution extends GuessGame { 11 public int guessNumber(int n) { 12 int left = 1, right = n; 13 while(left <= right){ 14 int mid = left + (right - left) / 2; 15 if (guess(mid) == -1){ 16 right = mid - 1; 17 }else if (guess(mid) == 1){ 18 left = mid + 1; 19 }else if (guess(mid) == 0){ 20 return mid; 21 } 22 } 23 //循环结束的条件是:left > right 24 //left= mid + 1, right = mid 25 return -1; 26 27 } 28 }
换一种方式的二分查找:
- while(left < right):这样循环结束的条件就是left == right,缩为了一个点,说明找到了答案,返回left或者right都可以;
- 当guess(mid) <= 0,表示猜对了或者猜大了,这时mid就可能为答案,让right = mid,搜索区间为[left, mid]
- 当guess(mid) > 0,表示猜小了,这时mid不可能为答案,需要移动左边界,让left = mid + 1,搜索区间为[mid+1,right]
- 这里的mid的计算方式为什么没有写成 mid = left + (right - left + 1) // 2(向上取整)?因为在这里根据循环内的语句,如果只有两个元素,mid == left,并不会进入[mid, right]的死循环,因此向下取整是可以的,即 mid = left + (right - left ) // 2。
python3代码:
# The guess API is already defined for you. # @param num, your guess # @return -1 if num is higher than the picked number # 1 if num is lower than the picked number # otherwise return 0 # def guess(num: int) -> int: class Solution: def guessNumber(self, n: int) -> int: left, right = 1, n while left < right: mid = left + (right - left) // 2 # 猜对了或者猜大了,区间变为[left, mid] if guess(mid) <= 0: right = mid else: # 猜小了,区间变为[mid + 1, right] left = mid + 1 # 循环结束的条件:left == right return left