#278
First Bad Version
Easy First true
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Versions 1..n are good up to some point and bad after it. Using an isBadVersion(v) API, find the first bad version with as few calls as possible.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: versions go good, good, …, bad, bad. Find the first bad.
Why this works: if mid is bad, the answer is mid or before; if good, it's after.
Example: n = 5, first bad = 4
mid 3 good → lo 4mid 4 bad → hi 4 → answer 4
✦Hints open one at a time
The answers look like F F F T T T. Find the first T.
If mid is bad, the answer is mid or earlier. If good, it's after mid.
↗Approach
Binary search with lo < hi: bad mid → hi = mid, good mid → lo = mid + 1. When lo == hi, that's the first bad version.
</>Solution (Java)
/* The isBadVersion API is defined in the parent class VersionControl. */
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; // mid could be the first bad one
else lo = mid + 1;
}
return lo;
}
}!Common mistake
(lo + hi) / 2 overflows when n is close to 2^31.
Complexity
- Time: O(log n).
- Space: O(1).
Topic: Binary Search
🎬 Episodes 21–23: video coming soon