Problem Statement:
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.
Approach:
- 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). - Loop ends when
l == r, which is the first bad version. Returnr.
Time & Space Complexity:
Time Complexity: O(logn)
Space Complexity: O(1)
Dry Run
Input: n = 5, first bad version = 4
Initial: l = 1, r = 5 n = 5, first bad version = 4 (isBadVersion(version) returns true if version >= 4, else false) Loop 1: m = 1 + Math.floor((5 - 1) / 2) = 3 isBadVersion(3) → false → l = m + 1 = 4 Loop 2: m = 4 + Math.floor((5 - 4) / 2) = 4 isBadVersion(4) → true → r = m = 4 Exit Loop: l < r → 4 < 4 → false → stop Return r = 4
Output: Result: 4
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;
};
};
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;
}
}
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;
}
}
