First Bad Version

Finding the first version of a release that introduced a bug is a classic real-world scenario. Imagine you have thousands of versions in continuous deployment, and you need to minimize the number of expensive integration tests. The First Bad Version problem is a perfect warm-up to demonstrate how binary search can dramatically reduce work.

Problem Statement

You have versions numbered 1 through n. There’s an API isBadVersion(version) which returns True if that version contains a bug (and every later version is also bad), or False otherwise. Implement a function firstBadVersion(n) that returns the smallest version number that is bad, while minimizing calls to isBadVersion.

1. Clarify Requirements Before Jumping Into Code

I want to be sure I fully understand:

• Versions go from 1 to n inclusive.

• Once a version is bad, every higher version is bad too.

• I should minimize calls to isBadVersion.

• n can be very large—so O(n) calls is too many.

• I return the version number (an integer), not a boolean.

2. Identify the Category of the Question

This is a search on a monotonic predicate problem over a numeric range, which maps directly to binary search on the version numbers. It’s not searching an array but a conceptual sorted “yes/no” space.

3. Consider a Brute-Force Approach to Understand the Problem

The simplest approach is to check every version from 1 up to n:

for v from 1 to n:
    if isBadVersion(v):
        return v

This works correctly, but in the worst case (first bad at n) it makes n calls—O(n) time. Too slow if n is huge.

4. Brainstorm More Solutions

I need to do fewer checks by exploiting the “all versions after a bad one are bad” property:

• Binary Search: Maintain left=1, right=n. Check mid. If mid is bad, move right=mid; otherwise left=mid+1. Repeat until left meets right. This uses O(log n) calls.

• Exponential + Binary Search: For unknown n, you can double a bound until you hit a bad version, then binary-search within that range. Here n is known, so simpler binary search suffices.

• Random Sampling: Not reliable for worst-case and violates minimal-call requirement.

• Parallel Checks: If you had parallelism, you could check multiple versions concurrently, but the interview focuses on single-threaded calls.

Binary search is the clear winner for minimal calls.

5. Discuss Trade-Offs Between Your Solutions

Approach	Calls to API	Time Complexity	Pros	Cons
Linear Scan	O(n)	O(n)	Trivial to implement	Too many API calls
Exponential + Binary	O(log n)	O(log n)	Handles unknown n	Extra complexity
Binary Search	O(log n)	O(log n)	Simple, minimal calls	Needs known n

Standard binary search achieves the goal cleanly.

6. Write Pseudocode to Structure Your Thoughts

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

7. Consider Edge Cases

• n = 1 and version 1 is bad → returns 1

• First bad at version 1 in a larger n → binary search narrows to left=1

• First bad at version n → left moves up until left = n

• All versions good (if API could behave that way)—problem assumes at least one bad exists

• Large n to ensure no overflow when computing mid (use left + (right-left)//2)

8. Write Full Code Syntax

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

9. Test Your Code

# Mock API for testing
bad = 4
def isBadVersion(v): return v >= bad

assert firstBadVersion(5) == 4
bad = 1
assert firstBadVersion(3) == 1
bad = 3
assert firstBadVersion(3) == 3
bad = 10
assert firstBadVersion(10) == 10
bad = 5
assert firstBadVersion(6) == 5

print("All tests passed!")

10. Key Lessons to Remember for Future Questions

• Whenever you search a monotonic “yes/no” predicate over a range, think binary search.

• Use mid = left + (right - left) // 2 to avoid integer overflow.

• Carefully choose whether to move left or right to avoid infinite loops.

• Checking the loop condition left < right ensures convergence.

• Always test edge cases: smallest range, first-at-start, first-at-end, and evenly split.

• Framing the problem as searching a boolean function (not just array indices) broadens binary search applicability.