LC 278 — First Bad Version

Problem

What are we solving?

Problem Statement

You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad.

You are given n versions [1, 2, ..., n] and a function isBadVersion(version) which returns whether a version is bad. Find the first bad version. You should minimise the number of calls to the API.

Example

Input:n = 5, bad = 4

Calls:isBadVersion(3)=false, isBadVersion(5)=true, isBadVersion(4)=true

Output:4

Intuition

The most explicit F→T pattern you'll ever see

Most binary search problems hide their boolean structure — you have to derive the condition yourself. Not here. The condition is the problem: isBadVersion() returns exactly the F/T array we need to binary search.

Once a build is bad, all subsequent builds inherit the bug and are also bad. The sequence goes F F F ... T T T exactly once. We just need to find the first T.

n = 8, first bad = 5

condition: isBadVersion(i)

v1F

v2F

v3F

v4F

v5T

v6T

v7T

v8T

Binary search finds v5 — the first bad version — in just 3 API calls instead of up to 8.

→

Why minimising API calls matters: Each isBadVersion() call is an expensive network request in a real CI system. Linear scan = O(n) calls. Binary search = O(log n) calls. For 1 billion versions, that's 1,000,000,000 calls vs just 30.

Step-by-step walkthrough

n = 8, first bad version = 5

1

left=1, right=8 → mid=4

isBadVersion(4) = false → condition FALSE. Search right: left = 5.

2

left=5, right=8 → mid=6

isBadVersion(6) = true → condition TRUE. Save boundary=6, search left: right = 5.

3

left=5, right=5 → mid=5

isBadVersion(5) = true → condition TRUE. Save boundary=5, search left: right = 4.

4

left=5 > right=4 → loop ends

Return boundary = 5. Correct! Only 3 API calls used.

Solution

Clean implementation

/* The isBadVersion API is defined in the parent class VersionControl.
   boolean isBadVersion(int version); */

public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        int left = 1;
        int right = n;
        int boundary = n; // at minimum, version n is bad

        while (left <= right) {
            // Use left + (right-left)/2 to avoid integer overflow
            int mid = left + (right - left) / 2;

            if (isBadVersion(mid)) {
                // condition TRUE: this might be the first bad version
                boundary = mid;
                right = mid - 1; // search left for an earlier bad version
            } else {
                // condition FALSE: first bad version is to the right
                left = mid + 1;
            }
        }

        return boundary;
    }
}

# The isBadVersion API is already defined — you just call isBadVersion(version)

class Solution:
    def firstBadVersion(self, n: int) -> int:
        left, right = 1, n
        boundary = n  # at minimum, version n is bad

        while left <= right:
            mid = left + (right - left) // 2

            if isBadVersion(mid):
                # condition TRUE: save and search left
                boundary = mid
                right = mid - 1
            else:
                # condition FALSE: search right
                left = mid + 1

        return boundary

!

Overflow trap: Never write mid = (left + right) / 2 when left and right can be close to Integer.MAX_VALUE. The sum overflows to a negative number. Always use left + (right - left) / 2. In Python this isn't an issue since integers are arbitrary precision, but it's a good habit.

Complexity

Time

O(log n)

Halves the version range each step. At most ⌈log₂ n⌉ API calls.

Space

O(1)

Three integer variables. No auxiliary structures.