LeetCode 第278题：第一个错误的版本

📖 文章摘要

本文详细解析LeetCode第278题“第一个错误的版本”，这是一道经典的二分查找问题。文章提供了二分查找的优化思路，包含C#、Python、C++三种语言实现，配有详细的查找过程分析表格和性能对比。适合学习二分查找算法的读者。

核心知识点： 二分查找、边界处理、API调用优化
难度等级： 简单
推荐人群： 初学算法的开发者，想要掌握二分查找技巧的读者

题目描述

你是产品经理，目前正在带领一个团队开发新的产品。不幸的是，你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的。

假设你有 n 个版本 [1, 2, ..., n]，你想找出导致之后所有版本出错的第一个错误的版本。

你可以通过调用 bool IsBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。

示例

示例 1：

输入：n = 5, bad = 4
输出：4
解释：
调用 IsBadVersion(3) -> false
调用 IsBadVersion(5) -> true
调用 IsBadVersion(4) -> true
第一个错误的版本是 4

示例 2：

输入：n = 1, bad = 1
输出：1

提示

1 <= bad <= n <= 2^31 - 1

解题思路

本题可以使用二分查找来解决，主要思路如下：

使用二分查找来定位第一个错误版本
如果当前版本是错误的，那么第一个错误版本一定在左边或者就是当前版本
如果当前版本是正确的，那么第一个错误版本一定在右边
通过不断缩小查找范围来定位第一个错误版本

图解思路

二分查找过程分析表

步骤	左边界	右边界	中间点	IsBadVersion(mid)	新边界	说明
初始	1	5	3	false	left=4	错误版本在右边
第二步	4	5	4	true	right=4	可能是第一个错误版本
结束	4	4	4	-	-	找到第一个错误版本

边界情况分析表

情况	输入	预期输出	处理方法	说明
只有一个版本	n=1	1	直接返回1	特殊情况处理
第一个就是错误版本	n=5, bad=1	1	二分查找正确处理	边界情况
最后一个是错误版本	n=5, bad=5	5	二分查找正确处理	边界情况

代码实现

C# 实现

public class Solution : VersionControl {
    public int FirstBadVersion(int n) {
        int left = 1;
        int right = n;
        
        while (left < right) {
            // 避免整数溢出的写法
            int mid = left + (right - left) / 2;
            
            if (IsBadVersion(mid)) {
                // 如果是错误版本，可能是第一个错误版本，继续向左找
                right = mid;
            } else {
                // 如果是正确版本，第一个错误版本在右边
                left = mid + 1;
            }
        }
        
        return left;
    }
}

Python 实现

class Solution:
    def firstBadVersion(self, n: int) -> int:
        left = 1
        right = n
        
        while left < right:
            # 避免整数溢出的写法
            mid = left + (right - left) // 2
            
            if isBadVersion(mid):
                # 如果是错误版本，可能是第一个错误版本，继续向左找
                right = mid
            else:
                # 如果是正确版本，第一个错误版本在右边
                left = mid + 1
                
        return left

C++ 实现

class Solution : public VersionControl {
public:
    int firstBadVersion(int n) {
        int left = 1;
        int right = n;
        
        while (left < right) {
            // 避免整数溢出的写法
            int mid = left + (right - left) / 2;
            
            if (isBadVersion(mid)) {
                // 如果是错误版本，可能是第一个错误版本，继续向左找
                right = mid;
            } else {
                // 如果是正确版本，第一个错误版本在右边
                left = mid + 1;
            }
        }
        
        return left;
    }
};

执行结果

C# 实现

执行用时：16 ms
内存消耗：15.1 MB

Python 实现

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

C++ 实现

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

性能对比

语言	执行用时	内存消耗	特点
C#	16 ms	15.1 MB	代码结构清晰，性能适中
Python	28 ms	14.8 MB	代码最简洁，但运行较慢
C++	0 ms	5.9 MB	性能最优，内存占用最小

代码亮点

🎯 使用二分查找将时间复杂度优化至O(log n)
💡 通过 left + (right - left) / 2 避免整数溢出
🔍 精确控制二分查找的边界条件
🎨 代码简洁清晰，注释完整

常见错误分析

🚫 使用 (left + right) / 2 可能导致整数溢出
🚫 边界条件处理不当，导致死循环
🚫 没有正确处理只有一个版本的情况
🚫 API调用次数过多，未达到最优解

解法对比

解法	时间复杂度	空间复杂度	优点	缺点
线性查找	O(n)	O(1)	实现简单	API调用次数多
二分查找	O(log n)	O(1)	API调用次数最少	需要注意边界条件
三分查找	O(log n)	O(1)	某些情况更快	实现复杂，不实用

📖 系列导航

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

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

💬 互动交流

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

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

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

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

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

📖 文章摘要

题目描述

示例

示例 1：

示例 2：

提示

解题思路

图解思路

二分查找过程分析表

边界情况分析表

代码实现

C# 实现

Python 实现

C++ 实现

执行结果

C# 实现

Python 实现

C++ 实现

性能对比

代码亮点

常见错误分析

解法对比

相关题目

📖 系列导航

💬 互动交流