难度: Easy
猜数字游戏的规则如下：
你可以通过调用一个预先定义好的接口 int guess(int num) 来获取猜测结果，返回值一共有 3 种可能的情况（-1，1 或 0）：
pick < numpick > numpick == 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 <= 231 - 11 <= pick <= n运行时间: 17 ms
内存: 15.9 MB
# 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)//2
if guess(mid)==0:
return mid
elif guess(mid)==-1:
right =mid-1
else:
left =mid+1
这道题使用二分查找的思路来猜数字。每次根据 guess 函数的返回值，缩小搜索范围，直到找到目标数字。如果 guess 返回 -1，说明猜的数字偏大，缩小右边界；如果返回 1，说明猜的数字偏小，缩小左边界；如果返回 0，说明猜中了，直接返回当前数字。
时间复杂度: O(log n)
空间复杂度: O(1)
# 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) // 2
if guess(mid) == 0:
# 猜中了，直接返回当前数字
return mid
elif guess(mid) == -1:
# 猜的数字偏大，缩小右边界
right = mid - 1
else:
# 猜的数字偏小，缩小左边界
left = mid + 1
在二分查找中，目标是找到一个特定的数字。当 guess 函数返回 0 时，这表示猜测的数字 mid 等于目标数字。因此，mid 是我们要找的准确数字，直接返回 mid 是因为已经确切地找到了所需的结果，无需进一步搜索。
二分查找通过每次将搜索范围减半来确保不会错过目标数字。当区间仅剩两个或三个数字时，算法逐步检查每个可能的位置（通过设置新的 left 或 right 边界），直到找到目标数字或区间缩小到一个元素。通过这种方法，即使区间很小，也能确保不会错过目标数字。
在某些编程语言中，直接使用 'left + right' 可能会在 left 和 right 都非常大时引起整数溢出。在 Python 中，整数类型支持大整数运算，因此理论上不会遇到这种溢出问题。但在其他一些语言中，如 Java 或 C++，建议使用 'left + (right - left) / 2' 来避免溢出。
当 guess(mid) 返回 -1 时，表示猜的数字大于目标数字，因此需要排除 mid 及其右边的所有数字，所以将 right 设置为 mid - 1。相反，当返回 1 时，表示猜的数字小于目标数字，需要排除 mid 及其左边的数字，因此将 left 设置为 mid + 1。这样的调整保证了每次都缩小搜索范围，有效地逼近目标数字。