猜数字大小

🎯 问题描述（来源于LeetCode）

描述：
我们正在玩猜数字游戏。猜数字游戏的规则如下：
我会从 1 到 n 随机选择一个数字。 请你猜选出的是哪个数字。（我选的数字在整个游戏中保持不变）。
如果你猜错了，我会告诉你，我选出的数字比你猜测的数字大了还是小了。
你可以通过调用一个预先定义好的接口 int guess(int num) 来获取猜测结果，返回值一共有三种可能的情况：

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

返回我选出的数字。
说明：

  • 1 <= n <= 231 - 1
  • 1 <= pick <= n

示例：

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

💻 解题思路

思路1：二分查找

思路1：代码实现

1
2
3
4
5
6
7
8
9
10
class Solution:
    def guessNumber(self, n: int) -> int:
        left,right=1,n
        while left<=right:
            mid=(left+right)//2
            if  guess(mid)==0:
                return mid
            elif guess(mid)<0:
                right=mid-1
            else: left=mid+1

思路1：📊 性能分析

提交结果
  • 运行时间：51ms击败33.43%
  • 内存消耗：18.97MB击败40.18%
复杂度验证
  • 时间复杂度：O(Logn)O(Logn)
  • 空间复杂度：O(1)O(1)

思考