Swift 二分查找实战：精准定位第一个“Bug版本”（LeetCode 278）

摘要

在版本迭代频繁的项目开发中，定位引入 bug 的第一个版本是一项高频任务。LeetCode 第278题“第一个错误的版本”就是这个经典问题的简化模型。本文将从题目理解、Swift 题解、代码实现分析到实际测试演示，手把手带你用最稳妥的方式搞定这类问题，同时也帮你理清二分查找的实际应用逻辑。

描述

题目场景是这样的：

你作为某个产品的质量管理工程师，产品有多个版本（从 1 到 n），某天你发现某个版本后产品开始出现 bug 了。幸运的是，团队内部已经有一个叫 isBadVersion(version) 的接口，能告诉你某个版本是不是坏的。

你的任务，就是在最少的 API 调用次数内，找出第一个出错的版本号。

示例

输入: n = 5, bad = 4
调用 isBadVersion(3) -> false
调用 isBadVersion(5) -> true
调用 isBadVersion(4) -> true

输出: 4

题解答案（Swift）

我们考虑使用二分查找。因为这个问题的特性就是一个“分界线”问题 —— 在某个版本之前是好的，之后全是坏的。

// 假设这是给定的 API，我们用它模拟判断
func isBadVersion(_ version: Int) -> Bool {
    return version >= badVersion  // 这个变量在测试中设置
}

func firstBadVersion(_ n: Int) -> Int {
    var left = 1
    var right = n
    
    while left < right {
        let mid = left + (right - left) / 2
        if isBadVersion(mid) {
            right = mid  // mid 可能是答案，往左边找
        } else {
            left = mid + 1  // 答案肯定在右边
        }
    }
    
    return left
}

题解代码分析

让我们分步骤来看看这个解法里发生了什么：

1. 初始化搜索区间
   left 是搜索的起点，right 是终点。我们从 [1, n] 这个闭区间里找答案。

2. 中点判断
   每次取中点 mid，调用 API：

   • 如果 isBadVersion(mid) 返回 true，说明第一个坏版本要么是 mid 本身，要么在它左边，我们继续缩小右边界；
   • 否则，第一个坏版本只能在 mid 的右边，更新左边界。

3. 终止条件
   当 left == right，我们就找到了那个“边界点”——第一个坏版本。

这种方法的优势在于它非常节省 API 调用次数，在 O(log n) 的时间复杂度下快速定位目标。

示例测试及结果

我们来跑一个小 demo：

// 用于模拟测试环境
var badVersion = 4  // 假设第4个版本开始是错误的
print(firstBadVersion(5))  // 输出应该是 4

输出结果：

4

你可以更改 badVersion 的值试试其他情况，比如设置为 1 或 5，都能精准返回第一个错误的版本。

时间复杂度分析

• 时间复杂度：O(log n)
  二分查找的每轮都把问题规模减半，最多只需要约 log2(n) 次调用 isBadVersion()。

空间复杂度分析

• 空间复杂度：O(1)
  我们只用了几个常量变量，没有用额外的存储空间。

总结

这道题虽然简单，但它展现了二分查找这个经典算法模型在实际开发中的应用价值。比如在日志回溯、异常回滚、CI/CD 构建定位问题时，经常会用到“找第一个出问题的点”的逻辑。
如果你能理解这里的逻辑，那在面对更复杂的查找或优化类问题时就能更得心应手。