278 - First Bad Version

Difficulty: Easy | Pattern: Binary Search | Company tags: Facebook, Amazon, Google

Problem Statement

You are a product manager and currently leading a team to develop a new product. You have n versions [1, 2, ..., n] and you want to find out the first bad one, which causes all the following ones to be bad.

You are given an API bool isBadVersion(version) which returns whether version is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.

Example 1:

Input: n = 5, bad = 4
Output: 4
Explanation: Versions: [good, good, good, bad, bad]

Example 2:

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

Algorithm Flow

Approach: Binary Search — O(log n)

Key insight: The versions form a pattern [good, good, ..., good, bad, bad, ..., bad]. Binary search finds the transition point. If the mid version is bad, the first bad might be mid or earlier. If good, the first bad is after mid.

def firstBadVersion(n: int) -> int:
    left, right = 1, n
    
    while left < right:
        mid = left + (right - left) // 2
        if isBadVersion(mid):
            right = mid      # first bad is at mid or earlier
        else:
            left = mid + 1   # first bad is after mid
    
    return left

Dry Run

n=5, bad=4

left	right	mid	isBad(mid)	action
1	5	3	False	left=4
4	5	4	True	right=4
4	4	—	left==right	return 4

4 ✓

Why mid = left + (right - left) // 2?

Avoids integer overflow. In Python this isn't necessary (arbitrary integers), but it's good practice shown in interviews.

Common Mistake: Using right = mid - 1

If mid is bad, we can't exclude it — it might BE the first bad version. So right = mid, not right = mid - 1. This is the standard "find left boundary" binary search template.

Complexity

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

Key Terms

Term	Definition
Binary search on answer space	Searching over a monotonic predicate (good→bad transition) rather than over a sorted array of values
Left-boundary template	Binary search variant that narrows [left, right] until left == right, converging on the first index where the predicate is true
Monotonic predicate	A boolean function (isBadVersion) whose result is false then true across the range, enabling binary search
Overflow-safe midpoint	Computing mid as left + (right - left) // 2 instead of (left + right) // 2 to avoid overflow in fixed-width integer languages

FAQ

1. Can this be solved without extra space? Yes — the iterative binary search uses only O(1) extra space (left, right, mid).
2. What if n = 1? The loop never executes since left == right == 1 immediately, and the function correctly returns 1 regardless of whether it's bad.
3. What if there is no bad version at all? The problem guarantees at least one bad version exists; without that guarantee, the algorithm would still return n, which would be incorrect and must be validated separately.
4. What's the follow-up interviewers usually ask? "What if isBadVersion is expensive or rate-limited?" — reinforces why minimizing calls via binary search (O(log n)) instead of linear scan (O(n)) matters.
5. How would this change if multiple discontinuities existed (not strictly monotonic)? Binary search would no longer be valid, since it depends on the good/bad sequence being monotonic; a linear scan would be required instead.

Quick Revision

• Versions form a monotonic sequence: all good, then all bad, with exactly one transition point.
• Binary search hunts for the leftmost index where isBadVersion is true — the "find left boundary" template.
• If isBadVersion(mid) is true, the answer could be mid or earlier, so set right = mid (never mid - 1).
• If false, the answer must be after mid, so set left = mid + 1.
• Loop until left == right; that value is the first bad version.
• Time complexity O(log n), space O(1) — far better than a linear scan.
• Use left + (right - left) // 2 to avoid integer overflow in languages with fixed-width ints.
• Edge case: n = 1 returns immediately without any API calls inside the loop.

Related Problems

• Binary search "find left/right boundary" template problems (e.g., search for first/last occurrence in a sorted array).
• Koko Eating Bananas / Capacity to Ship Packages — binary search on answer space applied to optimization problems rather than a boolean predicate.
• Any "minimize API calls with a monotonic predicate" problem shares this exact left-boundary binary search structure.