First Bad Version 题解：用二分查找在 O(log n) 内定位首个错误版本

First Bad Version 题解：用二分查找在 O(log n) 内定位首个错误版本

【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode

导读

本文基于 LeetCode 经典问题 278. First Bad Version，系统讲解如何在一段「先好后坏」的版本序列中，通过isBadVersion(version)API 精准定位第一个坏版本。全文覆盖暴力线性扫描、递归二分、迭代二分与下界（Lower Bound）收缩四种解法，并给出 Python、Java、C++、JavaScript、C#、Go、Kotlin、Swift、Rust 多语言实现与复杂度对比。读者学完后，既能直接 AC 本题，也能把「下界二分」模板迁移到任意单调判定场景（如寻找第一个满足条件的下标）。

前置知识

在动手解这道题之前，需要先掌握以下三个基础概念，它们也正是本题的考点：

• 二分查找（Binary Search）：在有序/单调的搜索空间中，每次把搜索区间减半，从而把线性查找降到对数复杂度。
• 避免整数溢出（Avoiding Integer Overflow）：计算中点时使用l + (r - l) / 2而非(l + r) / 2，防止l + r在接近Integer.MAX_VALUE时溢出为负数。
• 下界概念（Lower Bound）：在单调序列中找到第一个满足某条件的元素。本题「第一个坏版本」本质就是一个下界查询：isBadVersion的结果序列为false, false, ..., true, true, ...，要找到第一个true。

问题本质：单调性决定了二分可行

题目给出的 API 是isBadVersion(version) -> bool。核心前提是：一旦某个版本是坏的，它之后的所有版本也都是坏的。因此版本状态天然形成一段连续的false后接一段连续的true，这就是一个单调序列。

换句话说，我们面对的是一个形如下面的布尔数组：

目标是找到第一个true的下标（即版本 4）。正是因为这种「先假后真」的单调性，我们可以把「查找第一个坏版本」等价为「在单调布尔序列上做下界二分」，把时间复杂度从 $O(n)$ 降到 $O(\log n)$。

解法一：暴力线性搜索（Brute Force）

思路（Intuition）

最朴素的做法是从版本1开始逐个调用isBadVersion(i)，遇到的第一个坏版本就是答案。由于所有坏版本连续排在末尾，第一次遇到true即可返回。

算法步骤（Algorithm）

1. 从版本1遍历到n - 1。
2. 对每个版本调用isBadVersion(i)判断是否坏。
3. 返回第一个返回true的版本。
4. 若循环结束仍未找到，则n一定是首个坏版本，直接返回n。

多语言实现

Python

# The isBadVersion API is already defined for you. # def isBadVersion(version: int) -> bool: class Solution: def firstBadVersion(self, n: int) -> int: for i in range(1, n): if isBadVersion(i): return i return n

Java

/* The isBadVersion API is defined in the parent class VersionControl. boolean isBadVersion(int version); */ public class Solution extends VersionControl { public int firstBadVersion(int n) { for (int i = 1; i < n; i++) { if (isBadVersion(i)) { return i; } } return n; } }

C++

// The API isBadVersion is defined for you. // bool isBadVersion(int version); class Solution { public: int firstBadVersion(int n) { for (int i = 1; i < n; i++) { if (isBadVersion(i)) { return i; } } return n; } };

JavaScript

// The isBadVersion API is already defined in the VersionControl class. // isBadVersion(version: number): boolean class Solution extends VersionControl { /** * @param {number} n Total versions * @return {number} The first bad version */ firstBadVersion(n) { for (let i = 1; i < n; i++) { if (this.isBadVersion(i)) { return i; } } return n; } }

C#

/* The isBadVersion API is defined in the parent class VersionControl. bool IsBadVersion(int version); */ public class Solution : VersionControl { public int FirstBadVersion(int n) { for (int i = 1; i < n; i++) { if (IsBadVersion(i)) { return i; } } return n; } }

Go

/** * Forward declaration of isBadVersion API. * @param version your guess about first bad version * @return true if current version is bad * false if current version is good * func isBadVersion(version int) bool; */ func firstBadVersion(n int) int { for i := 1; i < n; i++ { if isBadVersion(i) { return i } } return n }

Kotlin

/* The isBadVersion API is defined in the parent class VersionControl. fun isBadVersion(version: Int): Boolean {} */ class Solution: VersionControl() { override fun firstBadVersion(n: Int): Int { for (i in 1 until n) { if (isBadVersion(i)) { return i } } return n } }

Swift

/** * The isBadVersion API is defined in the parent class VersionControl. * func isBadVersion(_ version: Int) -> Bool {} */ class Solution : VersionControl { func firstBadVersion(_ n: Int) -> Int { for i in 1..<n { if isBadVersion(i) { return i } } return n } }

Rust

// The API isBadVersion is defined for you. // isBadVersion(version: i32) -> bool; impl Solution { pub fn first_bad_version(&self, n: i32) -> i32 { for i in 1..n { if self.isBadVersion(i) { return i; } } n } }

时间复杂度与空间复杂度

• 时间复杂度：$O(n)$——最坏情况下需要调用n - 1次 API。
• 空间复杂度：$O(1)$ 额外空间。

当n很大（本题数据范围可达 $2^{31} - 1$）时，线性扫描会调用海量 API，必须改用二分。

解法二：递归二分搜索（Recursive Binary Search）

思路（Intuition）

既然版本序列满足「全好在前、全坏在后」的单调性，就可以用二分查找定位好坏边界。取中点m：

• 若isBadVersion(m)为true，说明首个坏版本在m处或更早，收缩到左半区间；
• 若为false，说明首个坏版本在m之后，收缩到右半区间。

每轮搜索区间减半，递归直到边界收敛。

算法步骤（Algorithm）

1. 定义递归辅助函数helper(l, r)，参数为左右边界。
2. 递归出口：若l > r，返回l作为首个坏版本。
3. 计算中点m = l + (r - l) / 2（防止溢出）。
4. 若isBadVersion(m)为true，递归搜索左半区间helper(l, m - 1)。
5. 否则递归搜索右半区间helper(m + 1, r)。
6. 从helper(1, n)开始搜索。

多语言实现

Python

# The isBadVersion API is already defined for you. # def isBadVersion(version: int) -> bool: class Solution: def firstBadVersion(self, n: int) -> int: def helper(l, r): if l > r: return l m = l + (r - l) // 2 if isBadVersion(m): return helper(l, m - 1) else: return helper(m + 1, r) return helper(1, n)

Java

/* The isBadVersion API is defined in the parent class VersionControl. boolean isBadVersion(int version); */ public class Solution extends VersionControl { public int firstBadVersion(int n) { return helper(1, n); } private int helper(int l, int r) { if (l > r) { return l; } int m = l + (r - l) / 2; if (isBadVersion(m)) { return helper(l, m - 1); } else { return helper(m + 1, r); } } }

C++

// The API isBadVersion is defined for you. // bool isBadVersion(int version); class Solution { public: int firstBadVersion(int n) { return helper(1, n); } private: int helper(int l, int r) { if (l > r) { return l; } int m = l + (r - l) / 2; if (isBadVersion(m)) { return helper(l, m - 1); } else { return helper(m + 1, r); } } };

JavaScript

// The isBadVersion API is already defined in the VersionControl class. // isBadVersion(version: number): boolean class Solution extends VersionControl { /** * @param {number} n Total versions * @return {number} The first bad version */ firstBadVersion(n) { const helper = (l, r) => { if (l > r) { return l; } const m = Math.floor(l + (r - l) / 2); if (this.isBadVersion(m)) { return helper(l, m - 1); } else { return helper(m + 1, r); } }; return helper(1, n); } }

C#

/* The isBadVersion API is defined in the parent class VersionControl. bool IsBadVersion(int version); */ public class Solution : VersionControl { public int FirstBadVersion(int n) { return Helper(1, n); } private int Helper(int l, int r) { if (l > r) { return l; } int m = l + (r - l) / 2; if (IsBadVersion(m)) { return Helper(l, m - 1); } else { return Helper(m + 1, r); } } }

Go

/** * Forward declaration of isBadVersion API. * @param version your guess about first bad version * @return true if current version is bad * false if current version is good * func isBadVersion(version int) bool; */ func firstBadVersion(n int) int { var helper func(l, r int) int helper = func(l, r int) int { if l > r { return l } m := l + (r-l)/2 if isBadVersion(m) { return helper(l, m-1) } else { return helper(m+1, r) } } return helper(1, n) }

Kotlin

/* The isBadVersion API is defined in the parent class VersionControl. fun isBadVersion(version: Int): Boolean {} */ class Solution: VersionControl() { override fun firstBadVersion(n: Int): Int { return helper(1, n) } private fun helper(l: Int, r: Int): Int { if (l > r) { return l } val m = l + (r - l) / 2 return if (isBadVersion(m)) { helper(l, m - 1) } else { helper(m + 1, r) } } }

Swift

/** * The isBadVersion API is defined in the parent class VersionControl. * func isBadVersion(_ version: Int) -> Bool {} */ class Solution : VersionControl { func firstBadVersion(_ n: Int) -> Int { return helper(1, n) } private func helper(_ l: Int, _ r: Int) -> Int { if l > r { return l } let m = l + (r - l) / 2 if isBadVersion(m) { return helper(l, m - 1) } else { return helper(m + 1, r) } } }

Rust

// The API isBadVersion is defined for you. // isBadVersion(version: i32) -> bool; impl Solution { pub fn first_bad_version(&self, n: i32) -> i32 { fn helper(sol: &Solution, l: i32, r: i32) -> i32 { if l > r { return l; } let m = l + (r - l) / 2; if sol.isBadVersion(m) { helper(sol, l, m - 1) } else { helper(sol, m + 1, r) } } helper(self, 1, n) } }

时间复杂度与空间复杂度

• 时间复杂度：$O(\log n)$——每轮搜索区间减半。
• 空间复杂度：$O(\log n)$——递归栈深度。

递归版逻辑清晰，但存在栈开销；在版本总量极大时，迭代版是更稳妥的选择。

解法三：迭代二分搜索（Iterative Binary Search，显式记录结果）

思路（Intuition）

迭代版二分维护l、r两个指针，并额外用一个res变量记录「当前遇到的最靠左的坏版本」。每次发现m是坏版本时，把它存进res并继续向左搜索，寻找是否存在更早的坏版本；若m是好版本则向右搜索。循环结束时res即为首个坏版本。

算法步骤（Algorithm）

1. 初始化l = 1、r = n、res = -1。
2. 当l <= r时循环：
   • 计算中点m = l + (r - l) / 2。
   • 若isBadVersion(m)为true：把m存入res，令r = m - 1向左搜索。
   • 否则令l = m + 1向右搜索。
3. 返回res作为首个坏版本。

多语言实现

Python

# The isBadVersion API is already defined for you. # def isBadVersion(version: int) -> bool: class Solution: def firstBadVersion(self, n: int) -> int: l, r = 1, n res = -1 while l <= r: m = l + (r - l) // 2 if isBadVersion(m): res = m r = m - 1 else: l = m + 1 return res

Java

/* The isBadVersion API is defined in the parent class VersionControl. boolean isBadVersion(int version); */ public class Solution extends VersionControl { public int firstBadVersion(int n) { int l = 1, r = n, res = -1; while (l <= r) { int m = l + (r - l) / 2; if (isBadVersion(m)) { res = m; r = m - 1; } else { l = m + 1; } } return res; } }

C++

// The API isBadVersion is defined for you. // bool isBadVersion(int version); class Solution { public: int firstBadVersion(int n) { int l = 1, r = n, res = -1; while (l <= r) { int m = l + (r - l) / 2; if (isBadVersion(m)) { res = m; r = m - 1; } else { l = m + 1; } } return res; } };

JavaScript

// The isBadVersion API is already defined in the VersionControl class. // isBadVersion(version: number): boolean class Solution extends VersionControl { /** * @param {number} n Total versions * @return {number} The first bad version */ firstBadVersion(n) { let l = 1, r = n, res = -1; while (l <= r) { const m = Math.floor(l + (r - l) / 2); if (this.isBadVersion(m)) { res = m; r = m - 1; } else { l = m + 1; } } return res; } }

C#

/* The isBadVersion API is defined in the parent class VersionControl. bool IsBadVersion(int version); */ public class Solution : VersionControl { public int FirstBadVersion(int n) { int l = 1, r = n, res = -1; while (l <= r) { int m = l + (r - l) / 2; if (IsBadVersion(m)) { res = m; r = m - 1; } else { l = m + 1; } } return res; } }

Go

/** * Forward declaration of isBadVersion API. * @param version your guess about first bad version * @return true if current version is bad * false if current version is good * func isBadVersion(version int) bool; */ func firstBadVersion(n int) int { l, r, res := 1, n, -1 for l <= r { m := l + (r-l)/2 if isBadVersion(m) { res = m r = m - 1 } else { l = m + 1 } } return res }

Kotlin

/* The isBadVersion API is defined in the parent class VersionControl. fun isBadVersion(version: Int): Boolean {} */ class Solution: VersionControl() { override fun firstBadVersion(n: Int): Int { var l = 1 var r = n var res = -1 while (l <= r) { val m = l + (r - l) / 2 if (isBadVersion(m)) { res = m r = m - 1 } else { l = m + 1 } } return res } }

Swift

/** * The isBadVersion API is defined in the parent class VersionControl. * func isBadVersion(_ version: Int) -> Bool {} */ class Solution : VersionControl { func firstBadVersion(_ n: Int) -> Int { var l = 1 var r = n var res = -1 while l <= r { let m = l + (r - l) / 2 if isBadVersion(m) { res = m r = m - 1 } else { l = m + 1 } } return res } }

Rust

// The API isBadVersion is defined for you. // isBadVersion(version: i32) -> bool; impl Solution { pub fn first_bad_version(&self, n: i32) -> i32 { let (mut l, mut r, mut res) = (1, n, -1); while l <= r { let m = l + (r - l) / 2; if self.isBadVersion(m) { res = m; r = m - 1; } else { l = m + 1; } } res } }

时间复杂度与空间复杂度

• 时间复杂度：$O(\log n)$。
• 空间复杂度：$O(1)$，只用常数个变量。

解法四：迭代二分搜索（Lower Bound 下界收缩）

思路（Intuition）

这是最优雅的模板：不再单独跟踪结果，而是让l与r直接收敛到首个坏版本。关键在于当m是坏版本时，用r = m把它保留在搜索区间内（而不是r = m - 1排除掉），因为m本身可能就是答案。当m是好版本时，用l = m + 1排除它。循环结束时l == r，二者共同指向首个坏版本。

算法步骤（Algorithm）

1. 初始化l = 1、r = n。
2. 当l < r时循环：
   • 计算中点m = l + (r - l) / 2。
   • 若isBadVersion(m)为true：首个坏版本在m或更早，令r = m。
   • 否则：首个坏版本在m之后，令l = m + 1。
3. 循环结束时l与r相等，返回l（或r）即为首个坏版本。

注意：l < r配合r = m时，中点计算m = l + (r - l) / 2取的是下中位数；当区间长度为 2（l = k, r = k + 1）时m = k，r = m可保证区间严格收缩，不会死循环。

多语言实现

Python

# The isBadVersion API is already defined for you. # def isBadVersion(version: int) -> bool: class Solution: def firstBadVersion(self, n: int) -> int: l, r = 1, n while l < r: m = l + (r - l) // 2 if isBadVersion(m): r = m else: l = m + 1 return l

Java

/* The isBadVersion API is defined in the parent class VersionControl. boolean isBadVersion(int version); */ public class Solution extends VersionControl { public int firstBadVersion(int n) { int l = 1, r = n; while (l < r) { int m = l + (r - l) / 2; if (isBadVersion(m)) { r = m; } else { l = m + 1; } } return r; } }

C++

// The API isBadVersion is defined for you. // bool isBadVersion(int version); class Solution { public: int firstBadVersion(int n) { int l = 1, r = n; while (l < r) { int m = l + (r - l) / 2; if (isBadVersion(m)) { r = m; } else { l = m + 1; } } return r; } };

JavaScript

// The isBadVersion API is already defined in the VersionControl class. // isBadVersion(version: number): boolean class Solution extends VersionControl { /** * @param {number} n Total versions * @return {number} The first bad version */ firstBadVersion(n) { let l = 1, r = n; while (l < r) { const m = Math.floor(l + (r - l) / 2); if (this.isBadVersion(m)) { r = m; } else { l = m + 1; } } return r; } }

C#

/* The isBadVersion API is defined in the parent class VersionControl. bool IsBadVersion(int version); */ public class Solution : VersionControl { public int FirstBadVersion(int n) { int l = 1, r = n; while (l < r) { int m = l + (r - l) / 2; if (IsBadVersion(m)) { r = m; } else { l = m + 1; } } return r; } }

Go

/** * Forward declaration of isBadVersion API. * @param version your guess about first bad version * @return true if current version is bad * false if current version is good * func isBadVersion(version int) bool; */ func firstBadVersion(n int) int { l, r := 1, n for l < r { m := l + (r-l)/2 if isBadVersion(m) { r = m } else { l = m + 1 } } return r }

Kotlin

/* The isBadVersion API is defined in the parent class VersionControl. fun isBadVersion(version: Int): Boolean {} */ class Solution: VersionControl() { override fun firstBadVersion(n: Int): Int { var l = 1 var r = n while (l < r) { val m = l + (r - l) / 2 if (isBadVersion(m)) { r = m } else { l = m + 1 } } return r } }

Swift

/** * The isBadVersion API is defined in the parent class VersionControl. * func isBadVersion(_ version: Int) -> Bool {} */ class Solution : VersionControl { func firstBadVersion(_ n: Int) -> Int { var l = 1 var r = n while l < r { let m = l + (r - l) / 2 if isBadVersion(m) { r = m } else { l = m + 1 } } return r } }

Rust

// The API isBadVersion is defined for you. // isBadVersion(version: i32) -> bool; impl Solution { pub fn first_bad_version(&self, n: i32) -> i32 { let (mut l, mut r) = (1, n); while l < r { let m = l + (r - l) / 2; if self.isBadVersion(m) { r = m; } else { l = m + 1; } } r } }

时间复杂度与空间复杂度

• 时间复杂度：$O(\log n)$。
• 空间复杂度：$O(1)$。

这也是四种解法中代码最精简、面试中最推荐的「下界二分」标准模板。

常见陷阱（Common Pitfalls）

陷阱一：计算中点时的整数溢出

直接写(l + r) / 2在l、r都接近Integer.MAX_VALUE时，l + r会溢出成负数，导致二分行为完全错误。必须使用l + (r - l) / 2（或语言等价写法），因为r - l不会溢出，从而保证中点计算安全。

陷阱二：循环条件的 Off-by-One 错误

混淆l < r与l <= r会导致结果错误或死循环：

• 使用l < r：循环在l == r时终止，此时两者共同指向答案，无需额外变量。
• 使用l <= r：循环会跨越到l > r，必须用单独变量（如解法三的res）记录最后找到的坏版本。

选一种模式并保持一致，同时确保边界更新（r = m与r = m - 1的选择）与循环条件匹配：

• l <= r配合r = m - 1（排除m，因为m已记录进res）；
• l < r配合r = m（保留m作为候选答案）。

仓库源码对照：从题解到可运行实现

本仓库在 python/0278-first-bad-version.py 中给出了与解法四完全一致的下界二分实现：

class Solution: def firstBadVersion(self, n: int) -> int: l, r = 1, n while l < r: v = (l + r) // 2 if isBadVersion(v): r = v else: l = v + 1 return l

C++ 实现 则附带了完整的题目说明与示例推演（n = 5, bad = 4）：

• 调用isBadVersion(3)返回false；
• 调用isBadVersion(5)返回true；
• 调用isBadVersion(4)返回true，最终返回4。

其核心逻辑使用int mid = left + (right - left) / 2安全求中点，并在right > left时持续收缩区间，注释明确标注Time: O(log n)、Space: O(1)。

Swift 实现 展示了同一下界思想的不同写法：从l = 0, r = n出发、使用l <= r循环并配合r = mid - 1，最终通过l + (r - l) / 2返回中点。这与解法三的「显式记录结果」思路同源，可以对照阅读，体会两种循环条件配对的差异。

四种解法横向对比

总结

First Bad Version 的核心价值在于把「二分查找」与「单调判定」结合：isBadVersion的结果天然满足单调性，因此问题被转化为标准的下界查询。掌握解法四的下界模板后，同类问题（如寻找第一个大于等于目标值的位置、二分答案类题目）都可以直接套用：当条件满足时保留当前候选r = m，不满足时排除l = m + 1，最终l即答案。同时牢记l + (r - l) / 2的安全中点写法与循环条件的配对规则，就能在面试与实战中稳定拿下这类「二分查找边界」问题。

【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode