First Bad Version

XXX. First Bad Version

Binary Search

Optimization

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 one, all the versions after a bad version are also bad.

Given an API bool isBadVersion(version), which returns whether a version is bad, implement a function to find the first bad version. Minimize the number of API calls.

Algorithm:

1. Use binary search to minimize the number of calls to isBadVersion().
2. Initialize two pointers: low to 1 (the first version) and high to n (the last version).
3. Calculate the mid-point between low and high.
4. Check if the mid-point is a bad version:
   • If true, update firstBadVersion to mid and move the high pointer to mid - 1 to search earlier versions.
   • If false, move the low pointer to mid + 1.
5. Repeat the process until low exceeds high.
6. Return firstBadVersion after the loop ends.

Complexity:

Time Complexity: O(log n), as binary search halves the search space with each iteration.
Space Complexity: O(1), as only a constant amount of extra space is used.

Java Implementation:

public int firstBadVersion(int n) {
    int low = 1;
    int high = n;
    int firstBadVersion = -1;

    while (low <= high) {
        int mid = (high - low) / 2 + low; // Calculate mid-point to avoid overflow
        if (isBadVersion(mid)) {
            firstBadVersion = mid; // Update result to current mid
            high = mid - 1; // Move to the left half
        } else {
            low = mid + 1; // Move to the right half
        }
    }

    return firstBadVersion;      
}
                

Python Implementation:

def firstBadVersion(n):
    low, high = 1, n
    first_bad_version = -1

    while low <= high:
        mid = low + (high - low) // 2  # Calculate mid-point
        if isBadVersion(mid):
            first_bad_version = mid  # Update result
            high = mid - 1  # Search in the left half
        else:
            low = mid + 1  # Search in the right half

    return first_bad_version
                

C++ Implementation:

int firstBadVersion(int n) {
    int low = 1, high = n;
    int first_bad_version = -1;

    while (low <= high) {
        int mid = low + (high - low) / 2; // Calculate mid-point
        if (isBadVersion(mid)) {
            first_bad_version = mid; // Update result
            high = mid - 1; // Search in the left half
        } else {
            low = mid + 1; // Search in the right half
        }
    }

    return first_bad_version;
}