This problem finds the first bad version in a sequence of versions from 1 to n. We have an API isBadVersion(version) that returns whether a version is bad. We use binary search to pinpoint the earliest bad version.
Steps
- Initialize pointers:
l = 1andr = n. - While
l < r:- Compute mid:
m = l + floor((r - l) / 2). - If
isBadVersion(m)is false → move right (l = m + 1). - Else (true) → move left or stay (
r = m).
- Compute mid:
- Loop ends when
l == r, which is the first bad version. - Return
r.
Dry Run
Input: n = 5, bad = 4
- l=1, r=5 → m=3 → isBad(3)=false → l=4
- l=4, r=5 → m=4 → isBad(4)=true → r=4
- l==r==4 → return 4
Output: 4
Input: n = 1, bad = 1
- l=1, r=1 → no loop → return 1
Output: 1
Time & Space Complexity
- Time Complexity: O(log n)
- Space Complexity: O(1)
var solution = function(isBadVersion) {
return function(n) {
let l = 1;
let r = n;
while (l < r) {
let m = l + Math.floor((r - l) / 2);
if (!isBadVersion(m)) {
l = m + 1;
} else {
r = m;
}
}
return r;
};
};
class Solution {
public:
int firstBadVersion(int n) {
int l = 1, r = n;
while (l < r) {
int m = l + (r - l) / 2;
if (!isBadVersion(m)) l = m + 1;
else r = m;
}
return r;
}
};
int firstBadVersion(int n) {
int l = 1, r = n;
while (l < r) {
int m = l + (r - l) / 2;
if (!isBadVersion(m)) l = m + 1;
else r = m;
}
return r;
}
public class Solution {
public int firstBadVersion(int n) {
int l = 1, r = n;
while (l < r) {
int m = l + (r - l) / 2;
if (!isBadVersion(m)) l = m + 1;
else r = m;
}
return r;
}
}
def firstBadVersion(n):
l, r = 1, n
while l < r:
m = l + (r - l) // 2
if not isBadVersion(m):
l = m + 1
else:
r = m
return r
public class Solution {
public int FirstBadVersion(int n) {
int l = 1, r = n;
while (l < r) {
int m = l + (r - l) / 2;
if (!IsBadVersion(m)) l = m + 1;
else r = m;
}
return r;
}
}
