First Bad Version — Left-Boundary Binary Search [LC 278, Meta Amazon Interview]

Problem Statement#

You are given n versions [1..n] and an API isBadVersion(v) returning whether a version is bad. All versions after a bad version are also bad. Find the first bad version while minimising API calls.

Constraints:

• 1 lessequal bad lessequal n lessequal 2^31 - 1

Input:  n = 5, bad = 4
Output: 4

Input:  n = 1, bad = 1
Output: 1

Why This Problem Matters#

LC 278 was famously used by Facebook (now Meta) as a phone screen and has since spread across Amazon, Microsoft, and countless mid-size companies. It matters for two reasons beyond its simplicity. First, it teaches the left-boundary binary search template — the variant that finds the first element satisfying a monotone condition. This template appears constantly in harder problems: minimum eating speed, smallest ship capacity, earliest day a task completes, first index where a condition becomes true.

Second, it teaches you to binary search without an array in memory. The "array" here is the version sequence and the predicate is the API call. You never touch elements directly. This is a common interview disguise: the search space is implicit, defined by a predicate rather than stored in memory. Recognising this is what turns a one-line FAANG O(log n) interview question into a teaching moment.

The constraint n lessequal 2^31 - 1 is a deliberate hint about overflow. Noticing it and using the safe midpoint formula impresses interviewers who explicitly look for production-ready awareness.

The Core Insight#

The version sequence has monotone structure: all good versions precede all bad versions. There is a single boundary — the first bad version — and everything after it is also bad. This is the signature of left-boundary binary search: a predicate P(v) is false for some prefix and true for the rest, and you want the first index where it becomes true.

If isBadVersion(mid) is true, mid might be the first bad version, so keep mid in the search space by setting hi = mid (not mid - 1). If false, mid is definitely good, so exclude it via lo = mid + 1. Because hi = mid shrinks while keeping the candidate, use while lo lt hi to avoid an infinite loop when lo == hi.

Visual Dry Run#

For n = 10, bad = 7:

Only 4 API calls for 10 versions. With n equal one billion, only 30 calls.

Solution (Optimal)#

class Solution:
    def firstBadVersion(self, n: int) -> int:
        lo, hi = 1, n                       # versions are 1-indexed
        while lo < hi:                       # converge to single candidate
            mid = lo + (hi - lo) // 2       # overflow-safe for n up to 2^31-1
            if isBadVersion(mid):
                hi = mid                    # keep mid as candidate
            else:
                lo = mid + 1                # exclude mid, it is good
        return lo                            # lo equals hi equals first bad

var solution = function(isBadVersion) {
    return function(n) {
        let lo = 1;
        let hi = n;
        while (lo < hi) {
            const mid = lo + Math.floor((hi - lo) / 2);
            if (isBadVersion(mid)) {
                hi = mid;                    // keep mid as candidate
            } else {
                lo = mid + 1;               // exclude good version
            }
        }
        return lo;                           // first bad version
    };
};

Time: O(log n) — at most ceil(log2(n)) API calls; 31 calls for n = 2^31 - 1. Space: O(1) — only integer variables.

Common Mistakes#

• Using hi = mid - 1 discards the candidate and may skip the actual first bad version.
• Pairing while lo lessequal hi with hi = mid causes an infinite loop when lo == hi.
• Calling isBadVersion twice per iteration doubles API calls — call once.
• Starting lo = 0 introduces a non-existent version 0; versions are 1-indexed.
• Using (lo + hi) / 2 overflows when n is close to 2^31 - 1 in static-typed languages.

Interview Tips#

• Acknowledge the 2^31 - 1 constraint and point out the overflow risk.
• State the predicate explicitly: "isBadVersion is monotone false-to-true."
• Walk through n = 1 to show the loop never executes and lo = 1 is returned.
• Emphasise that the API is called exactly once per iteration.
• Compare API call count to a linear scan to highlight log n savings.

Follow-up Questions#

• What if there is no bad version? The constraint forbids it, but you would post-check isBadVersion(lo) after the loop.
• How is this related to bisect_left? Identical in concept — find the leftmost index where a predicate is true.
• What if the predicate is not monotone? Binary search no longer applies; use a linear scan or different structure.
• What if versions are non-sequential identifiers? Map them to a 0..n-1 index and binary search on the index.

Key Takeaways#

• First Bad Version is the canonical left-boundary binary search problem.
• The template uses while lo lt hi with hi = mid on true and lo = mid + 1 on false.
• When the loop exits, lo == hi is the answer — return either.
• The single character difference from classic search (hi = mid vs hi = mid - 1) defines the pattern.
• API calls are O(log n) — 31 calls for two billion versions.
• Always use the overflow-safe midpoint when constraints allow n near 2^31.
• This template generalises to predicate search where data lives behind an API.