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这就是一个单调序列。换句话说我们面对的是一个形如下面的布尔数组版本号12345isBadVersionfalsefalsefalsetruetrue目标是找到第一个true的下标即版本 4。正是因为这种「先假后真」的单调性我们可以把「查找第一个坏版本」等价为「在单调布尔序列上做下界二分」把时间复杂度从 $O(n)$ 降到 $O(\log n)$。解法一暴力线性搜索Brute Force思路Intuition最朴素的做法是从版本1开始逐个调用isBadVersion(i)遇到的第一个坏版本就是答案。由于所有坏版本连续排在末尾第一次遇到true即可返回。算法步骤Algorithm从版本1遍历到n - 1。对每个版本调用isBadVersion(i)判断是否坏。返回第一个返回true的版本。若循环结束仍未找到则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 nJava/* 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定义递归辅助函数helper(l, r)参数为左右边界。递归出口若l r返回l作为首个坏版本。计算中点m l (r - l) / 2防止溢出。若isBadVersion(m)为true递归搜索左半区间helper(l, m - 1)。否则递归搜索右半区间helper(m 1, r)。从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(m1, 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初始化l 1、r n、res -1。当l r时循环计算中点m l (r - l) / 2。若isBadVersion(m)为true把m存入res令r m - 1向左搜索。否则令l m 1向右搜索。返回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 resJava/* 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初始化l 1、r n。当l r时循环计算中点m l (r - l) / 2。若isBadVersion(m)为true首个坏版本在m或更早令r m。否则首个坏版本在m之后令l m 1。循环结束时l与r相等返回l或r即为首个坏版本。注意l r配合r m时中点计算m l (r - l) / 2取的是下中位数当区间长度为 2l k, r k 1时m kr 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 lJava/* 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已记录进resl 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 lC 实现 则附带了完整的题目说明与示例推演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返回中点。这与解法三的「显式记录结果」思路同源可以对照阅读体会两种循环条件配对的差异。四种解法横向对比解法核心思想时间复杂度空间复杂度适用建议暴力线性搜索从 1 逐个调用 API$O(n)$$O(1)$仅用于理解题意递归二分递归收缩区间$O(\log n)$$O(\log n)$逻辑直观注意栈开销迭代二分记录结果l rres变量$O(\log n)$$O(1)$边界清晰、易调试迭代二分下界l rr m收敛$O(\log n)$$O(1)$面试推荐模板代码最简总结First Bad Version 的核心价值在于把「二分查找」与「单调判定」结合isBadVersion的结果天然满足单调性因此问题被转化为标准的下界查询。掌握解法四的下界模板后同类问题如寻找第一个大于等于目标值的位置、二分答案类题目都可以直接套用当条件满足时保留当前候选r m不满足时排除l m 1最终l即答案。同时牢记l (r - l) / 2的安全中点写法与循环条件的配对规则就能在面试与实战中稳定拿下这类「二分查找边界」问题。【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考