First Bad Version — Classic Binary Search

The Problem

You have n versions, numbered 1 to n. A function isBadVersion(v) returns True if version v is bad. Once a version is bad, all later versions are also bad. Find the first bad version. Minimize the number of API calls.

The bad-version function is monotonic: once it starts returning True, it never goes back. That’s the structure binary search needs.

Intuition

Bad versions form a monotonic suffix of the version range. So the predicate isBadVersion(v) is False on a prefix and True from some boundary onward — the textbook “leftmost True” binary search. Maintain [lo, hi] such that the answer is always in that range. On a True midpoint, the answer is in [lo, mid] (mid included). On a False midpoint, the answer is in [mid + 1, hi]. The loop ends when lo == hi, which is the answer.

Explanation with Example

Take n = 5, with versions 4 and 5 bad.

version: 1 2 3 4 5
bad?:    F F F T T

lo=1 hi=5 mid=3 isBad(3)=False -> lo=4
lo=4 hi=5 mid=4 isBad(4)=True  -> hi=4
lo=4 hi=4 return 4

Three API calls instead of four for a linear scan, and the gap grows logarithmically with n.

Code

Two details matter. First, the midpoint uses lo + (hi - lo) // 2 instead of (lo + hi) // 2 to avoid integer overflow in languages with 32-bit ints (Python doesn’t care). Second, we use lo < hi and update hi = mid (not hi = mid - 1) because mid itself might be the answer.

def firstBadVersion(n):
    lo, hi = 1, n
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if isBadVersion(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo

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;
            } else {
                lo = mid + 1;
            }
        }
        return lo;
    }
}

// The API bool isBadVersion(int version); is defined for you.
class Solution {
public:
    int firstBadVersion(int n) {
        int lo = 1, hi = n;
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (isBadVersion(mid)) {
                hi = mid;
            } else {
                lo = mid + 1;
            }
        }
        return lo;
    }
};

Edge Cases

If n = 1, the loop body doesn’t execute and we return 1 — which is correct if version 1 is bad. The problem guarantees at least one bad version exists, so we never return a fake answer.

If the first version is bad, the search converges to 1 in O(log n) calls. If the last version is the only bad one, it converges to n.

Negative or zero version numbers aren’t possible by the spec, so we don’t handle them.

Complexity Analysis

Time is O(log n) API calls. Each iteration halves the range. Space is O(1): two integers.

The number of calls is exactly ceil(log2(n)) in the worst case, which for n = 2^31 - 1 is 31. Compared to potentially 2 billion linear calls, this is an enormous saving.

How to Explain It in an Interview

Lead with: “Bad versions form a monotonic suffix of the version range. I’ll binary search for the leftmost bad version. The invariant is that the answer is in [lo, hi]. When isBadVersion(mid) is True, the answer is in [lo, mid]. When it’s False, the answer is in [mid + 1, hi].”

Mention the overflow-safe midpoint as a small detail that distinguishes a careful candidate. Note the loop condition lo < hi, not lo <= hi, because we converge when both pointers meet and that meeting point is the answer.

Walk through a five-version example. Finish with O(log n) calls and O(1) space.

Related Problems

• Search Insert Position — leftmost-true binary search variant.
• Find First and Last Position of Element in Sorted Array.
• Binary Search — vanilla version.
• Valid Perfect Square — binary search on a value.