LeetCode 374题 “猜数字大小”（Guess Number Higher or Lower）是一个经典的二分查找问题。题目描述如下：

题目描述：

我们正在玩一个猜数字游戏。游戏规则如下：

• 我从1到n选择一个数字。你来猜我选了哪个数字。
• 每次你猜错了，我会告诉你这个数字是大了还是小了。

你调用一个预先定义好的接口 int guess(int num)，它会返回三个可能的结果：

• -1：我选的数字比你猜的小
• 1：我选的数字比你猜的大
• ：恭喜！你猜对了！

示例：

输入: n = 10, 我选择 6

你的猜测序列应该是 1, 2, 5, 7, 6

解题思路：

这个问题可以通过二分查找来解决。二分查找是一种高效的查找算法，适用于有序数组。在这个问题中，虽然我们没有具体的数组，但我们可以将数字范围 [1, n] 看作一个有序数组。

具体步骤：

1. 初始化两个指针 left 和 right，分别指向范围的最小值和最大值，即 left = 1 和 right = n。
2. 在 left 和 right 之间进行二分查找：
   • 计算中间值 mid，即 mid = (left + right) // 2。
   • 使用 guess(mid) 来判断中间值与目标值的关系。
   • 根据 guess 的返回值调整 left 和 right：
     • 如果 guess(mid) == 0，说明猜对了，返回 mid。
     • 如果 guess(mid) == -1，说明目标值小于 mid，将 right 调整为 mid - 1。
     • 如果 guess(mid) == 1，说明目标值大于 mid，将 left 调整为 mid + 1。
3. 重复步骤2，直到找到目标值。

代码实现：

# The guess API is already defined for you.

class Solution: def guessNumber(self, n: int) -> int: left, right = 1, n while left <= right: mid = (left + right) // 2 result = guess(mid) if result == 0: return mid elif result == -1: right = mid - 1 else: left = mid + 1 return -1 # This line should never be reached if the input is valid

解释：

• left 和 right 分别初始化为 1 和 n，表示搜索范围。
• 在循环中，计算中间值 mid。
• 根据 guess(mid) 的返回值调整搜索范围。
• 当 guess(mid) == 0 时，表示找到了目标值，直接返回 mid。
• 循环直到 left 超过 right，理论上在有效输入下不会出现这种情况。

复杂度分析：

• 时间复杂度： O(log n)，二分查找的时间复杂度为对数级别。
• 空间复杂度： O(1)，只使用了常数级别的额外空间。

通过这种方式，我们可以高效地解决这个猜数字问题。希望这个解释对你有帮助！如果有更多问题，欢迎继续提问。