First Bad Version (LeetCode 278)

The problem

You have versions 1, 2, …, n of a product. At some point one version went bad, and every version after a bad one is also bad. You can call isBad(v), which says whether version v is bad. Return the first bad version, using as few calls as possible.

In the code below, the API is simulated by passing the real answer bad and defining isBad(v) as v >= bad.

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

Versions 1 to 3 are good, versions 4 and 5 are bad, so the first bad one is 4.

How to think about it

Start with brute force. Call isBad(1), isBad(2), … until one is bad. That is O(n) calls. With n up to 2³¹ − 1, that could be two billion API calls.

Look at the shape of the answers. Read isBad across all versions and you get good, good, …, good, bad, bad, …, bad. Once it flips, it never flips back. That is a monotonic yes/no sequence, and the answer is the position of the first yes.

The key insight: test the middle and keep the half that still contains the boundary. If mid is bad, the first bad version is mid or earlier, so set hi = mid (don’t throw mid away; it might be the answer). If mid is good, the first bad version is strictly later, so set lo = mid + 1. Stop when lo == hi: that single remaining version is the answer.

Which pattern is this? Binary search on a boundary, the “first true” template with while lo < hi. The tell is any monotonic predicate: false then true, and you want the switch point. This template reappears in Koko Eating Bananas and every “search on the answer” problem.

Approach

1. Set lo = 1 and hi = n. The first bad version is somewhere in [lo, hi].
2. While lo < hi:
   • mid = (lo + hi) // 2.
   • If isBad(mid), set hi = mid.
   • Else set lo = mid + 1.
3. Return lo.

Solution

def first_bad_version(n, bad):
    def isBad(v): return v >= bad    # given by the API in the real problem
    lo, hi = 1, n
    while lo < hi:                   # stop when one candidate remains
        mid = (lo + hi) // 2
        if isBad(mid): hi = mid      # mid could be the first bad one: keep it
        else: lo = mid + 1           # mid is good: answer is after it
    return lo
# first_bad_version(5, 4) -> 4

Dry run

On n = 5, first bad version 4:

Now lo == hi == 4, so the answer is 4, found with two API calls.

Complexity

• Time: O(log n). Each call halves the range of candidates, so about 31 calls cover n = 2³¹ − 1.
• Space: O(1).

Edge cases and pitfalls

• n = 1: the loop never runs and the answer is 1 (the problem guarantees a bad version exists).
• First version is bad: hi keeps shrinking to 1.
• Last version is bad: lo keeps climbing to n.
• hi = mid - 1 when mid is bad can skip the answer. In the boundary template, the side that may contain the answer keeps mid.
• while lo <= hi with hi = mid loops forever once lo == hi. Use lo < hi with this template.
• Overflow in other languages: compute lo + (hi - lo) // 2, since lo + hi can exceed 2³¹ − 1.

Related problems

• Search Insert Position (LeetCode 35): the same first-true boundary, with ”nums[i] >= target” as the test.
• Koko Eating Bananas (LeetCode 875): the test is “can she finish at this speed?” and you search over speeds.
• Find Minimum in Rotated Sorted Array (LeetCode 153): the same lo < hi, hi = mid template on a rotated array.