First Bad Version
Find the first bad version with the fewest isBadVersion calls by binary searching for the first true in a false-then-true sequence.
Problem Understanding
First Bad Version: you have versions 1..n. Once a version is bad, every later version is bad too. Using the API isBadVersion(version), find the first bad version while making as few calls as possible.
Example: n = 5, first bad = 4: isBadVersion(3) is false, isBadVersion(4) is true, so the answer is 4.
The Intuition: Find the First True
Line the versions up and write each one's verdict: good, good, good, bad, bad. That is a sorted sequence of booleans, so binary search finds the boundary in O(log n) calls:
- Check
mid. - Bad: the first bad version is
midor earlier. Keepmid:hi = mid. - Good: the first bad version is after
mid:lo = mid + 1. - When
lo == hi, you are standing on it.
This "first index where a condition becomes true" template also solves Search Insert Position and Sqrt(x) from the other side.
Interactive Walkthrough
Each version is a cell. The search cannot see which ones are bad, so a verdict appears only once a version is checked: ✓ for good, ✗ for bad. The range [lo, hi] is tinted. Try First is bad and Last is bad: both take only 4 calls for 16 versions.
Dry Run Table
Input: n = 5, first bad = 4
| lo | hi | mid | isBadVersion(mid) | Move |
|---|---|---|---|---|
| 1 | 5 | 3 | false | lo = 4 |
| 4 | 5 | 4 | true | hi = 4 |
lo = hi = 4. Answer: 4, found with 2 calls.
The Solution Template
Find-first-true binary search. isBadVersion is provided by LeetCode in every language.
First Bad Version Code
1var solution = function(isBadVersion) {2 return function(n) {3 let lo = 1, hi = n;4 while (lo < hi) {5 const mid = lo + Math.floor((hi - lo) / 2);6 if (isBadVersion(mid)) hi = mid;7 else lo = mid + 1;8 }9 return lo;10 };11};
Edge Cases & Common Mistakes
- n = 1: the only version must be the bad one; the loop does not run.
- Overflow:
(lo + hi) / 2overflows for n near 2³¹ − 1; uselo + (hi − lo) / 2. hi = mid − 1on a bad mid: can skip the answer when mid is the first bad version.while (lo <= hi)withhi = mid: loops forever once lo equals hi; uselo < hi.- Scanning from version 1: correct but O(n) API calls; the problem asks for the minimum.
Summary
isBadVersion goes false, then true, so binary search for the first true: a bad mid stays in the range (hi = mid), a good mid is skipped (lo = mid + 1). Compute mid as lo + (hi − lo) / 2 to avoid overflow. O(log n) calls and O(1) space.
More practice: DSA interview questions with answers · patterns cheat sheet