First Bad Version
First Bad Version: versions 1..n are built in order and one bad version spoils every later one. Using the isBadVersion(v) API, find the first bad version with as few calls as possible.
- 1 <= bad <= n <= 2³¹ - 1
- isBadVersion(version) returns whether that version is bad
- Minimise the number of calls to the API
Intuition
A bad version poisons everything after it, so the answers to isBadVersion read false, false, …, true, true — the pattern flips exactly once. That single switch point is the answer, and finding a switch in a monotone sequence is binary search. The array is never inspected; only the boundary matters, which is why this problem is really about the predicate rather than the data.
The tell is a yes/no test that, once it flips, never flips back — a monotone predicate over an ordered space. When you see that, stop thinking about the data and search the predicate. Koko Eating Bananas, Capacity to Ship Packages, and Split Array Largest Sum are the same problem with a computed predicate instead of an API.
Approach
Before reading on: write down why a false result lets you discard everything to the left, and why a true result does not let you discard mid itself. Then pick a loop condition that avoids one final confirming API call.
Monotonicity is the precondition, not a detail
Binary search is only valid when one probe tells you which side the answer lies on. Here that guarantee comes from the problem statement: all the versions after a bad version are also bad. This makes the predicate isBadVersion(v) monotone — once true it stays true. Without that property a false result would say nothing about later versions and the whole method collapses into a linear scan. Recognising the monotone predicate is the actual insight; the loop that follows is mechanical.
Keep the candidate, discard the rest
Maintain lo = 1, hi = n, with the invariant that the first bad version lies in [lo, hi]. Probe mid. If isBadVersion(mid) is true, mid may itself be the first bad version, so it must be kept: set hi = mid. If it is false, mid and everything before it are good, so set lo = mid + 1. The asymmetry is deliberate — the true branch keeps mid while the false branch excludes it, and that is what makes the search converge on the boundary instead of overshooting it.
Terminating without a confirming call
Use while lo < hi. When the loop exits, lo == hi and the invariant says the answer is in that one-element range, so lo is returned with no extra probe. That matters here more than usual: the problem frames each API call as expensive, and a version of the loop written with lo <= hi would spend a final unnecessary call confirming what the invariant already guarantees. The total is ⌈log₂ n⌉ calls — about 31 even when n is the full 2³¹ - 1.
Solution & live demo
Common pitfalls
Excluding mid when the probe returns bad
if isBadVersion(mid):
hi = mid - 1if isBadVersion(mid):
hi = midmid being bad does not prove an earlier version is bad — mid may be the first one. Dropping it discards the answer, and the search settles one position too far left.
Looping while lo <= hi
while lo <= hi:
...
hi = midwhile lo < hi:
...
hi = midWith hi = mid the range stops shrinking once lo == hi == mid, so the loop never exits. The condition and the update must match the same interval convention.
Overflowing the midpoint
int mid = (lo + hi) / 2;
int mid = lo + (hi - lo) / 2;
n can be 2³¹ - 1, so lo + hi exceeds the signed 32-bit range and wraps negative in C++ and Java, producing an invalid version number.
Edge cases
Every probe reports bad, so hi walks down to 1.
Every probe reports good, so lo climbs to n.
lo == hi immediately, the loop never runs, and 1 is returned with zero API calls.
The midpoint must be lo + (hi - lo) / 2 or the sum overflows a 32-bit int.
One probe at mid = 1 reports good, lo moves to 2, and the loop ends.