First Bad Version
Problem statement
You have n versions of a product, numbered 1 to n, and one of them is the first version that broke something. Every version built after that one is broken too, because each version is built on top of the one before it.
You are given a function isBadVersion(version) that tells you whether a given version is broken. Calling it is the expensive part — think of it as running a full check, or asking a real deployment whether it is healthy — so find the first broken version using as few calls as you can.
A useful way to picture it: if you wrote down isBadVersion(1), isBadVersion(2), ..., isBadVersion(n), you would see a run of false values followed by a run of true values, with no true ever appearing before another true that came before it. Your job is to find exactly where that run of true begins.
Examples
Example 1
Input: n = 5, bad = 4
Output: 4
Explanation: Versions 1, 2 and 3 are good and version 4 is the first bad one, so every version from 4 onward (4 and 5) is also bad.
Example 2
Input: n = 1, bad = 1
Output: 1
Explanation: There is only one version, and it is the bad one, so it is also the first bad version.
Hints
Approach
Optimal: Binary search
Intuition
Because every version before "bad" is good and every version from "bad" onward is bad, asking isBadVersion(version) is really asking "has the pattern flipped to bad yet, at or before this point?" That single yes/no split is exactly what binary search is built for — it does not need a sorted array, only a condition that goes from false to true and never back.
Keep a window [left, right] that is guaranteed to contain the first bad version. Look at the middle of the window. If it is bad, the answer is mid or something earlier, so shrink the window down to that left half, keeping mid itself since it could be the answer. If it is good, the answer must come later, so move past mid. Each check throws away half of what is left, which is what makes this so much faster than checking one version at a time.
Steps
- Set
left = 1andright = n. - While
left < right:- Compute
mid = left + (right - left) / 2(this form avoids integer overflow for very largen). - If
isBadVersion(mid)is true, the first bad version ismidor earlier, so setright = mid. - Otherwise the first bad version is after
mid, so setleft = mid + 1.
- Compute
- When
left == right, that value is the first bad version — returnleft.
Dry run
n = 5, bad = 4
| step | left | right | mid | isBadVersion(mid) | action |
|---|---|---|---|---|---|
| 1 | 1 | 5 | 3 | false | left = 4 |
| 2 | 4 | 5 | 4 | true | right = 4 |
| 3 | 4 | 4 | — | loop ends | return 4 |
Edge cases: when n = 1, left already equals right, so the loop never runs and 1 is returned right away. When bad = 1, the very first mid check already comes back true, and the window keeps shrinking from the left end without ever wasting a call on a version that could not be the answer.
What makes this faster than the brute force scan is that every single call removes half of the remaining versions, instead of removing just one.
Complexity
Time O(log n) - Every call to isBadVersion cuts the remaining window in half, so after roughly log2(n) calls only one version is left. For n close to a billion that is about 30 calls instead of up to a billion, which is the whole reason this pattern is asked whenever a problem says "minimize the number of calls".
Space O(1) - Only two pointers and a midpoint are kept in memory, no matter how large n is.
# LeetCode provides isBadVersion(version) for you; this mock stands in for it
# here so the file runs on its own.
_bad = 4 # change this to try other cases
def isBadVersion(version: int) -> bool:
return version >= _bad
class Solution:
def firstBadVersion(self, n: int) -> int:
left, right = 1, n
while left < right:
mid = left + (right - left) // 2
if isBadVersion(mid):
right = mid
else:
left = mid + 1
return left
if __name__ == "__main__":
_bad = 4
print(Solution().firstBadVersion(5)) # 4
_bad = 1
print(Solution().firstBadVersion(1)) # 1RecapThe whole problem in a few lines, for the night before
- Spot it: a problem says "minimize the number of calls" and gives you a check that is false for a while, then true from some point on
- Idea: binary search on the version number itself — shrink
[left, right]usingisBadVersion(mid), keepingmidwhen it's bad - Cost: O(log n) time, O(1) space (a plain left-to-right scan is O(n) time)
- Trap: setting
right = mid - 1whenmidis bad throws away the version that might be the actual answer — useright = midinstead
Interview follow-ups
What if you are not given n, and isBadVersion could return true for any positive integer?
Use exponential (galloping) search first: check version 1, then 2, then 4, then 8, doubling each time, until isBadVersion finally returns true at some version v. The first bad version must lie between v/2 and v, so run the normal binary search inside that window. This costs O(log(bad)) calls in total, close to what you'd get if you had known the true upper bound from the start.
What if you need to find the first bad version among several independent products at once?
Run the same binary search separately for each product; the calls for different products don't share any state, so they can be issued in parallel instead of one after another. Total work stays O(k log n) for k products, but wall-clock time drops close to O(log n) if the isBadVersion checks can run concurrently.
Frequently asked questions
Binary search does not actually need a sorted array — it only needs a condition that is false for a while and then stays true, with no going back to false. Reading isBadVersion(1) through isBadVersion(n) gives exactly that pattern, so the same shrinking-window idea that works on a sorted array works here too, just against a function call instead of an index.
For very large n (the constraints allow n up to 2^31 - 1), left + right can overflow a 32-bit integer before the division happens, giving a wrong, sometimes negative, midpoint. Writing it as left + (right - left) / 2 keeps every intermediate value within a safe range. It is a small habit worth keeping for any binary search over large inputs.
It mirrors two real situations directly: bisecting a range of commits to find the one that broke a build (which is literally how git bisect works), and finding the first canary batch of a rollout that starts failing health checks. In both cases each check is costly, so minimizing calls is the actual goal, not just an interview constraint.
No — that would throw away mid even though mid itself might be the first bad version. Because the goal is to find that exact version rather than search for a target value that may or may not exist, the window must shrink to right = mid so mid stays a candidate until the loop proves something better.
That is exactly when the O(log n) approach earns its keep. If each call means running a real deployment health check or replaying a build, cutting the number of calls from potentially millions down to around 20 or 30 is the difference between a check that finishes in seconds and one that takes hours.