12.1 First Bad Version

12.1.1 Problem Metadata

12.1.2 Description

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.

Suppose 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.

12.1.3 Examples

Example 1:

Input: n = 5, bad = 4
Output: 4
Explanation:
call isBadVersion(3) -> false
call isBadVersion(5) -> true
call isBadVersion(4) -> true
Then 4 is the first bad version.

Example 2:

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

12.1.4 Constraints

  • \(1 \le \text{bad} \le n \le 2^{31} - 1\)

12.1.5 Solution - Binary Search

12.1.5.1 Walkthrough

This is a classic binary search problem with an interactive twist - we’re searching for the first occurrence of a “bad” version in a sorted sequence where all versions after the first bad one are also bad.

Core Strategy:

The key insight is that the versions form a monotonic sequence: once we hit a bad version, all subsequent versions are bad. This property makes binary search ideal:

[good, good, good, BAD, bad, bad, bad]
                   ↑
            first bad version

Binary Search Logic:

At each step: 1. Check the middle version mid 2. If isBadVersion(mid) is true: - mid could be the first bad version, OR - The first bad version is somewhere to the left of mid - Search the left half: [left, mid-1] - But also check if mid-1 is good (if so, mid is the answer) 3. If isBadVersion(mid) is false: - mid is good, so the first bad version must be to the right - Search the right half: [mid+1, right]

Why Binary Search?

  • Minimize API calls: Binary search reduces the search space by half each iteration
  • Time complexity: O(log n) vs O(n) for linear search
  • Optimal: With n versions, we need at most log₂(n) calls to the API

Step-by-step execution for n=5, bad=4:

Initial: [1, 2, 3, 4, 5]  l=1, r=5

Step 1: mid = 1 + (5-1)/2 = 3
  isBadVersion(3) = false → search right half
  l=4, r=5

Step 2: mid = 4 + (5-4)/2 = 4
  isBadVersion(4) = true
  isBadVersion(3) = false → found it! Return 4

Edge Cases Handled:

  1. First version is bad (bad=1): Binary search will converge to 1
  2. Last version is bad (bad=n): Binary search will check all the way to n
  3. Large n values (\(2^{31}-1\)): Using mid = l + (r-l)/2 prevents integer overflow

12.1.5.2 Analysis

  • Time Complexity: O(log n)
    • Binary search halves the search space each iteration
    • At most log₂(n) calls to isBadVersion()
    • This is optimal for this problem - we cannot do better than O(log n)
  • Space Complexity: O(log n)
    • Recursive implementation uses O(log n) call stack space
    • Each recursive call stores local variables (l, r, mid)
    • Iterative version would be O(1) space

Why This is Optimal:

  • Must minimize API calls - binary search achieves O(log n) calls
  • Cannot determine the answer without querying - must make at least log n queries in worst case
  • The monotonic property of the problem makes binary search applicable

12.1.5.3 Implementation Steps

Initialization: 1. Set search range: left = 1, right = n

Binary Search (Recursive): 2. Base case: If right < left, return -1 (no bad version found) 3. Calculate middle: mid = left + (right - left) / 2 (avoids overflow) 4. Check if mid is bad: - Call isBadVersion(mid) - If true (mid is bad): - Check if this is the first bad version: !isBadVersion(mid - 1) - If yes, return mid - If no, search left half: binarySearch(left, mid - 1) - If false (mid is good): - First bad version must be on the right - Search right half: binarySearch(mid + 1, right)

Return: 5. Return the index of the first bad version

12.1.5.4 Code - Java

public int firstBadVersion(int n) {
    return binarySearch(1, n);
}

private int binarySearch(int l, int r) {
    if (r < l) {
        return -1;
    }

    int mid = l + (r - l) / 2;

    if (isBadVersion(mid)) {
        // Found a bad version - check if it's the first one
        if (!isBadVersion(mid - 1)) {
            return mid;
        }

        // Find the first bad version between l...mid-1
        return binarySearch(l, mid - 1);
    } else {
        // mid is good, search the right half
        return binarySearch(mid + 1, r);
    }
}