江川个人博客FIELD NOTES / 个人知识库

Article / 文章

LeetCode 第374题：猜数字大小

猜数字游戏的规则如下： - 每轮游戏，我都会从 1 到 n 随机选择一个数字。请你猜选出的是哪个数字。 - 如果你猜错了，我会告诉你，你猜测的数字比我选出的数字是大了还是小了。 你可以通过调用一个预先定义好的接口 int guess(int num) 来获取猜测结果，返回值一共有 3 种可能的情况（-1，1 或 0）： - -1：我选出的数字比你猜的数字小

📖 文章摘要

本文详细解析LeetCode第374题“猜数字大小”，这是一道二分查找问题。文章提供了基于二分查找的解法，包含C#、Python、C++三种语言实现，配有详细的算法分析和性能对比。适合想要提升二分查找应用能力的读者。

核心知识点： 二分查找、分治算法 难度等级： 简单 推荐人群： 具有基础算法知识，想要提升二分查找应用能力的程序员

题目描述

猜数字游戏的规则如下：

  • 每轮游戏，我都会从 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

提示

  • 1 <= n <= 2^31 - 1
  • 1 <= pick <= n

解题思路

本题可以使用二分查找解决：

  1. 定义左右边界
  2. 计算中间值
  3. 根据guess结果调整边界
  4. 重复直到找到目标值

时间复杂度： O(log n) 空间复杂度： O(1)

图解思路

二分查找过程

步骤 左边界 右边界 中间值 guess结果 说明
1 1 10 5 1 目标值大于5
2 6 10 8 -1 目标值小于8
3 6 7 6 0 找到目标值

边界调整

情况 左边界调整 右边界调整 说明
guess = 1 mid + 1 不变 目标值在右半部分
guess = -1 不变 mid - 1 目标值在左半部分
guess = 0 返回mid 返回mid 找到目标值

代码实现

C# 实现

public class Solution : GuessGame {
    public int GuessNumber(int n) {
        int left = 1;
        int right = n;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            int result = guess(mid);
            
            if (result == 0) {
                return mid;
            } else if (result == 1) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        return -1;
    }
}

Python 实现

class Solution:
    def guessNumber(self, n: int) -> int:
        left, right = 1, n
        
        while left <= right:
            mid = left + (right - left) // 2
            result = guess(mid)
            
            if result == 0:
                return mid
            elif result == 1:
                left = mid + 1
            else:
                right = mid - 1
                
        return -1

C++ 实现

class Solution {
public:
    int guessNumber(int n) {
        int left = 1;
        int right = n;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            int result = guess(mid);
            
            if (result == 0) {
                return mid;
            } else if (result == 1) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        return -1;
    }
};

执行结果

C# 实现

  • 执行用时：36 ms
  • 内存消耗：14.8 MB

Python 实现

  • 执行用时：28 ms
  • 内存消耗：13.2 MB

C++ 实现

  • 执行用时：0 ms
  • 内存消耗：5.9 MB

性能对比

语言 执行用时 内存消耗 特点
C++ 0 ms 5.9 MB 执行效率最高，内存占用最小
Python 28 ms 13.2 MB 代码简洁，内存占用适中
C# 36 ms 14.8 MB 类型安全，内存占用较大

代码亮点

  1. 🎯 使用二分查找优化搜索
  2. 💡 避免整数溢出
  3. 🔍 处理边界情况
  4. 🎨 代码结构清晰，易于维护

常见错误分析

  1. 🚫 整数溢出
  2. 🚫 边界条件处理错误
  3. 🚫 循环条件错误
  4. 🚫 返回值错误

解法对比

解法 时间复杂度 空间复杂度 优点 缺点
二分查找 O(log n) O(1) 高效，避免溢出 实现较复杂
线性搜索 O(n) O(1) 直观，易于理解 时间复杂度高

相关题目

📖 系列导航

🔥 算法专题合集 - 查看完整合集

📢 关注合集更新：点击上方合集链接，关注获取最新题解！目前已更新第374题。

💬 互动交流

感谢大家耐心阅读到这里！希望这篇题解能够帮助你更好地理解和掌握这道算法题。

如果这篇文章对你有帮助，请：

  • 👍 点个赞，让更多人看到这篇文章
  • 📁 收藏文章，方便后续查阅复习
  • 🔔 关注作者，获取更多高质量算法题解
  • 💭 评论区留言，分享你的解题思路或提出疑问

你的支持是我持续分享的动力！

💡 一起进步：算法学习路上不孤单，欢迎一起交流学习！