First Bad Version

How it works

This is a cleaner binary search variant that finds the lower bound. Instead of tracking the result separately, we shrink the search range until l and r converge to the first bad version. When we find a bad version at m, we keep it in our search range by setting r = m rather than excluding it.

Steps

1. Initialize l = 1 and r = n.
2. While l < r:
   • Calculate middle m = l + (r - l) / 2.
   • If isBadVersion(m) is true, the first bad version is at m or earlier, so set r = m.
   • Otherwise, the first bad version is after m, so set l = m + 1.
3. When the loop ends, l equals r and points to the first bad version.

Complexity

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

Things to watch for

Integer Overflow When Calculating Midpoint

Using (l + r) / 2 to calculate the midpoint can cause integer overflow when l and r are large values. For example, if both are close to Integer.MAX_VALUE, their sum overflows to a negative number. Always use l + (r - l) / 2 or the equivalent in your language to safely compute the midpoint.

Off-by-One Errors in Loop Conditions

Confusing l < r with l <= r leads to incorrect results or infinite loops. With l < r, the loop terminates when l == r, which points to the answer. With l <= r, you need a separate variable to track the result. Choose one pattern and apply it consistently, ensuring your boundary updates (r = m vs r = m - 1) match your loop condition.

# The isBadVersion API is already defined for you.
# def isBadVersion(version: int) -> bool:

class Solution:
    def firstBadVersion(self, n: int) -> int:
        l, r = 1, n
        while l < r:
            m = l + (r - l) // 2
            if isBadVersion(m):
                r = m
            else:
                l = m + 1
        return l

// The API isBadVersion is defined for you.
// bool isBadVersion(int version);

class Solution {
public:
    int firstBadVersion(int n) {
        int l = 1, r = n;
        while (l < r) {
            int m = l + (r - l) / 2;
            if (isBadVersion(m)) {
                r = m;
            } else {
                l = m + 1;
            }
        }
        return r;
    }
};