First Bad Version (LC 278)

Pattern: Binary Search (Boundary — First True)
Difficulty: Easy
Key Concept: Monotone predicate: versions 1..k are good, k+1..n are bad; binary search for the smallest bad version.

Problem Statement

You are a product manager building a system with n versions labeled 1 through n. A version after some point is broken.

You are given an API boolean isBadVersion(int version) that returns whether that version is bad.

Implement a function to find the first bad version — the smallest version in [1, n] such that isBadVersion(version) is true.

You must minimize the number of calls to isBadVersion.

Input: int n
Output: int — first bad version in [1, n]

1. Algorithm & Pseudocode

Brute force

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

Optimal (boundary binary search)

left = 1, right = n
while left < right:
    mid = left + (right - left) / 2
    if isBadVersion(mid):
        right = mid      // first bad is at mid or to the left
    else:
        left = mid + 1   // first bad is to the right of mid
return left

2. Step-by-Step Analysis (Beginner-Friendly)

Monotonicity
If version b is bad, every version > b is bad. If version g is good, every version < g is good. That lets you discard half the range each time.
Why while (left < right)
You are not looking for an arbitrary “equal” value in an array; you shrink until left and right meet at the first index where isBadVersion is true. The loop invariant: the answer is always in [left, right].
When isBadVersion(mid) is true
mid might be the first bad, or an even later bad — never an earlier one. So set right = mid to keep mid in the search space.
When isBadVersion(mid) is false
All versions <= mid are good, so the first bad is at least mid + 1 → left = mid + 1.
Overflow
n can be up to 2^31 - 1. In Java, left + right can overflow int. Always use mid = left + (right - left) / 2.
Interview pattern
This is the classic “find first position where predicate holds” template — same shape as lower-bound style problems.

3. The Dry Run

Assumption: n = 5, first bad version bad = 4
So: isBadVersion(1..3) = false, isBadVersion(4) = isBadVersion(5) = true.

Step	`left`	`right`	`mid`	`isBadVersion(mid)`	Action
init	1	5	—	—	enter `while left < right`
1	1	5	3	false	`left = 4`
2	4	5	4	true	`right = 4`
3	4	4	—	—	`left == right` → exit

Return left → 4.

4. Java Solution

Brute Force

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

public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        for (int v = 1; v <= n; v++) {
            if (isBadVersion(v)) {
                return v;
            }
        }
        return n;
    }
}

Time: O(n) API calls in worst case. Space: O(1).

Optimal

/* 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;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (isBadVersion(mid)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
}

Time: O(log n) API calls. Space: O(1).

5. The “Java vs. Others” Edge

Overflow: With n near Integer.MAX_VALUE, (left + right) / 2 overflows; left + (right - left) / 2 does not. This is essential in Java int arithmetic.
Python: Integers do not overflow like Java int, but the safe mid formula is still recommended for clarity and porting.
C++: Use long long for mids, or the same safe formula with care on types; unsigned helps for some bounds.
Pattern name: Boundary / first-true binary search — pairs mentally with LC 35’s “insertion point” and LC 34’s leftmost/rightmost tweaks.

6. Complexity Summary

Approach	Time	Space	Notes
Brute Force	O(n) calls	O(1)	Linear scan from 1.
Optimal	O(log n) calls	O(1)	Halves `[left, right]` each step; overflow-safe `mid`.