First Bad Version
Find the first index where isBadVersion(i) becomes true — boundary binary search.
3 min read
binary-search
Problem#
Versions 1..n; once a version is bad, all later ones are too. Given isBadVersion(version), find the first bad one.
Examples#
n = 5, bad = 4→4n = 1, bad = 1→1
Constraints#
1 <= bad <= n <= 2^31 - 1.
Approach#
Boundary binary search. lo, hi initially 1, n. While lo < hi, mid = lo + (hi - lo) / 2; if isBadVersion(mid), the answer is at most mid (hi = mid); else (lo = mid + 1).
Solution#
class Solution {public: int firstBadVersion(int n) { int lo = 1, hi = n; while (lo < hi) { int mid = lo + (hi - lo) / 2; if (isBadVersion(mid)) hi = mid; else lo = mid + 1; } return lo; }};// isBadVersion is provided by the LeetCode runtime.func firstBadVersion(n int) int { lo, hi := 1, n for lo < hi { mid := lo + (hi-lo)/2 if isBadVersion(mid) { hi = mid } else { lo = mid + 1 } } return lo}# isBadVersion is provided by the LeetCode runtime.class Solution: def firstBadVersion(self, n: int) -> int: lo, hi = 1, n while lo < hi: mid = lo + (hi - lo) // 2 if isBadVersion(mid): hi = mid else: lo = mid + 1 return lo// isBadVersion is provided by the LeetCode runtime.var solution = function(isBadVersion) { return function(n) { let lo = 1, hi = n; while (lo < hi) { const mid = lo + Math.floor((hi - lo) / 2); if (isBadVersion(mid)) hi = mid; else lo = mid + 1; } return lo; };};// isBadVersion is provided by the LeetCode runtime.public class Solution extends VersionControl { public int firstBadVersion(int n) { int lo = 1, hi = n; while (lo < hi) { int mid = lo + (hi - lo) / 2; if (isBadVersion(mid)) hi = mid; else lo = mid + 1; } return lo; }}// isBadVersion is provided by the LeetCode runtime.declare function isBadVersion(version: number): boolean;
const solution = (isBadVersion: (v: number) => boolean) => { return function(n: number): number { let lo = 1, hi = n; while (lo < hi) { const mid = lo + Math.floor((hi - lo) / 2); if (isBadVersion(mid)) hi = mid; else lo = mid + 1; } return lo; };};Editorial#
The lo < hi template is for finding the first index satisfying a monotone predicate. hi = mid (not mid - 1) keeps the candidate in the search range; lo = mid + 1 eliminates a confirmed non-answer. Loop invariant: answer ∈ [lo, hi].
Complexity#
- Time: O(log n).
- Space: O(1).
Concept revision#
Related#