OJ-leetcode-374. 猜数字大小（简单二分查找）

港控/mmm° 2022-12-26 00:52 165阅读 0赞

**目录**

题目

思路

代码

更优题解

--------------------

# 题目 #

猜数字游戏的规则如下：

每轮游戏，我都会从 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.com/problems/guess-number-higher-or-lower

# 思路 #

二分查找

# 代码 #

# The guess API is already defined for you.
    # @param num, your guess
    # @return -1 if my number is lower, 1 if my number is higher, otherwise return 0
    # def guess(num: int) -> int:
    
    class Solution:
        def guessNumber(self, n: int) -> int:
            low = 1
            high = n
            if n<1:
                return -1
            if guess(n)==0:
                return n
            if guess(1)==0:
                return 1
            while low<=high:
                mid = low + (high-low)//2
                if guess(mid)==0:
                    return mid
                if guess(mid)==-1:
                    high = mid-1
                else:
                    low = mid+1
            return -1

判断边界是为了打败更多的人，数字大的话判断n和1还是很省时间的

# 更优题解 #

三分查找，java版（[官方题解][Link 1]）

/* The guess API is defined in the parent class GuessGame.
       @param num, your guess
       @return -1 if my number is lower, 1 if my number is higher, otherwise return 0
          int guess(int num); */
    
    public class Solution extends GuessGame {
        public int guessNumber(int n) {
            int low = 1;
            int high = n;
            while (low <= high) {
                int mid1 = low + (high - low) / 3;
                int mid2 = high - (high - low) / 3;
                int res1 = guess(mid1);
                int res2 = guess(mid2);
                if (res1 == 0)
                    return mid1;
                if (res2 == 0)
                    return mid2;
                else if (res1 < 0)
                    high = mid1 - 1;
                else if (res2 > 0)
                    low = mid2 + 1;
                else {
                    low = mid1 + 1;
                    high = mid2 - 1;
                }
            }
            return -1;
        }
    }

更多内容：[OJ网站题目分类，分难度整理笔记（leetcode、牛客网）][OJ_leetcode]

更多python相关内容：[【python总结】python学习框架梳理][python_python]

喜欢本文的请动动小手点个赞，收藏一下，有问题请下方评论，转载请注明出处，并附有原文链接，谢谢！如有侵权，请及时联系。如果您感觉有所收获，自愿打赏，可选择支付宝18833895206（小于），您的支持是我不断更新的动力。

[Link 1]: https://leetcode-cn.com/problems/guess-number-higher-or-lower/solution/cai-shu-zi-da-xiao-by-leetcode/
[OJ_leetcode]: https://blog.csdn.net/lady_killer9/article/details/108273799
[python_python]: https://blog.csdn.net/lady_killer9/article/details/108763489