摘要

“猜数字”听起来像是个小游戏，但在算法题里，它其实考察的是 二分查找 的应用。
这道题的核心就是如何高效地通过“反馈提示”把范围缩小，最终锁定答案。
今天这篇文章里，我会用 Swift 实现完整的解法，并且结合实际场景来看看，这样的思路在现实系统中也很常见。

描述

我们在玩一个猜数字游戏，规则是这样的：

• 系统会在 1 到 n 之间随机挑选一个数字 pick。

• 我们每次猜一个数字 num，系统会通过 guess(num) 给出反馈：

  • 返回 -1：说明 num > pick。
  • 返回 1：说明 num < pick。
  • 返回 0：说明猜中了！

任务是：编写一个函数 guessNumber(n)，返回系统选中的数字。

举个例子：

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

可以看到，这就是一个很典型的 带提示的查找问题。

题解答案

最直观的解法是暴力枚举，从 1 开始逐个猜，直到猜对为止。
但是如果 n 特别大（比如接近 2³¹），暴力枚举会非常慢。

更聪明的做法是：

• 每次猜范围的中点（mid）。
• 如果太大，就往左边找；如果太小，就往右边找。
• 这个过程和二分查找一模一样，时间复杂度是 O(log n)，效率极高。

题解代码分析

下面给出 Swift 代码实现：

// 假设这是系统提供的 API
// 实际在 LeetCode 中已经内置
var pick = 6
func guess(_ num: Int) -> Int {
    if num == pick { return 0 }
    return num > pick ? -1 : 1
}

class Solution {
    func guessNumber(_ n: Int) -> Int {
        var left = 1
        var right = n
        
        while left <= right {
            let mid = left + (right - left) / 2
            let res = guess(mid)
            
            if res == 0 {
                return mid // 猜中了
            } else if res < 0 {
                right = mid - 1 // 猜大了
            } else {
                left = mid + 1 // 猜小了
            }
        }
        
        return -1 // 理论上不会走到这里
    }
}

代码解析

1. guess(_ num: Int) 模拟系统 API，返回三种可能的结果。

2. 在 guessNumber(_ n: Int) 方法里：

   • left 和 right 定义了搜索区间。
   • 每次取中点 mid，调用 guess(mid) 来缩小范围。
   • 根据反馈调整区间边界，直到找到答案。

3. mid 的计算用了 left + (right - left) / 2，避免了 left + right 溢出的问题。

示例测试及结果

我们来跑几个测试：

let solution = Solution()

pick = 6
print(solution.guessNumber(10))  // 输出: 6

pick = 1
print(solution.guessNumber(1))   // 输出: 1

pick = 1
print(solution.guessNumber(2))   // 输出: 1

运行结果：

6
1
1

完全符合题意。

时间复杂度

• 每次查找都把区间缩小一半。
• 最坏情况下需要查找 log₂(n) 次。
• 时间复杂度：O(log n)。

空间复杂度

• 只用了常数级别的变量 left、right、mid。
• 空间复杂度：O(1)。

总结

这道题本质上就是一个二分查找的应用题，思路很直接，但考察点在于：

• 是否能够把问题转化为“逐步缩小范围”。
• 是否能写出稳健的二分查找代码，避免死循环或溢出问题。

在实际开发中，这种思路应用非常广：

• 数据库索引查找：通过二分快速定位某一条数据。
• 猜测范围问题：比如二分查找最小满足条件的值。
• 游戏玩法设计：类似“你猜数字，我给提示”的机制，可以在逻辑上映射到二分查找。

可以说，这道题是“算法世界里的 Hello World”，简单但很经典。