First Bad Version

A product has versions numbered 1 to n. At some point a defect was introduced, and since each version builds on the previous one, every version from that point on is bad as well. So the versions look like a run of good ones followed by a run of bad ones, and at least version n is bad.

You cannot inspect versions directly. Instead your function receives n and a function isBadVersion(v), which returns true if version v is bad. Return the number of the first bad version.

Each call is expensive, so the judge allows at most 66 calls per test; checking versions one by one will exceed that for large n. In the examples the second value is the hidden first bad version that drives isBadVersion; your function never sees it directly.

Example 1

Example 2

Example 3

Constraints

• 1 <= bad <= n <= 231 - 1
• isBadVersion may be called at most 66 times per test.

Pattern Path · Binary Search · problem 58 of 169

Start simple

Call isBadVersion on 1, 2, 3, ... until it returns true: O(n) calls, far too many when n is around two billion.

The key idea

The answers of isBadVersion over 1..n look like false, false, ..., false, true, true, ..., true. The task is to find the boundary in a sorted sequence of booleans, which is exactly what binary search does well.

Keep a range [lo, hi] with the invariant "the first bad version lies in this range". It starts as [1, n], which is valid because version n is bad. Check the middle version mid:

• if it is bad, the first bad version is mid or earlier, so set hi = mid (not mid - 1, which could throw away the answer);
• if it is good, every version up to mid is good, so set lo = mid + 1.

Because mid is rounded down and lo < hi, both updates shrink the range, so the loop ends with lo == hi: the answer. About 31 calls suffice for n near 2³¹. In languages with 32-bit integers, compute mid = lo + (hi - lo) / 2, because lo + hi can overflow.

Complexity

• Time: O(log n)
• Space: O(1)

Python

class Solution:
    def firstBadVersion(self, n, isBadVersion):
        lo, hi = 1, n                # the first bad version is always in [lo, hi]
        while lo < hi:
            mid = lo + (hi - lo) // 2
            if isBadVersion(mid):
                hi = mid             # mid might be the first bad one, so keep it
            else:
                lo = mid + 1         # everything up to mid is good
        return lo

JavaScript

var firstBadVersion = function(n, isBadVersion) {
  let lo = 1;
  let hi = n;                    // the first bad version is always in [lo, hi]
  while (lo < hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (isBadVersion(mid)) {
      hi = mid;                  // mid might be the first bad one, so keep it
    } else {
      lo = mid + 1;              // everything up to mid is good
    }
  }
  return lo;
};

What the interviewer is checking

This tests binary search on a predicate rather than an array: choosing the right invariant, the lo/hi updates that never skip the answer, and overflow-safe midpoints.

Mistakes to avoid

• Setting hi = mid - 1 when mid is bad, which can skip the first bad version.
• Computing (lo + hi) / 2 in 32-bit integer arithmetic, which overflows when n is close to 2,147,483,647.
• Calling isBadVersion twice per step (for mid and mid - 1), which doubles the number of calls.

Follow-ups to expect

• What if checking a version costs different amounts? (Weight the split point by cost.)
• How does git bisect use the same idea? (Halving commits between good and bad.)
• What if results are flaky? (Repeat checks, or use a noisy binary search.)

In real software

git bisect finds the commit that introduced a bug in exactly this way, and the same search finds the first failing build, config value or data threshold in a sorted range.

Practice next