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.

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.

Input

• n: An integer representing the number of versions (1-indexed, so versions are 1, 2, ..., n).
• isBadVersion(version): A boolean API that returns true if the given version is bad, and false otherwise.

Output

• Return the smallest version number such that isBadVersion(version) == true.

Examples

Example 1:

Input: n = 5, bad = 4
Output: 4

Explanation:
           +-----+-----+-----+-----+-----+
 version = |  1  |  2  |  3  |  4  |  5  |
           +-----+-----+-----+-----+-----+
     Bad =  False False False  True  True

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

Explanation:
           +-----+
 version = |  1  |
           +-----+
     Bad =  True

call isBadVersion(1) -> true
Then 1 is the first bad version.

Different Approaches

1️⃣ Binary Search

Intuition:

The problem involves finding the first bad version in a range of versions. Once a version is identified as bad, all subsequent versions are guaranteed to be bad. This gives the problem a monotonic property: if version i is bad then all versions j where j ≥ i are also bad.

The goal is to find the smallest index of a bad version while minimizing the number of calls to the isBadVersion API. A binary search is ideal because it allows us to repeatedly divide the search range in half, efficiently narrowing down the first bad version.

Approach:

1. Define the Search Space: Start with the entire range of versions from 1 to n.
2. Binary Search:

   • Calculate the middle version (mid) using the formula:

     mid = low + (high - low) / 2

   • Use the API isBadVersion(mid) to check whether the current version is bad.
     • If it's bad:
       • This could be the first bad version, so store it as a candidate.
       • Narrow the search to the left half by updating high = mid - 1.
     • If it's not bad:
       • The first bad version must be in the right half, so update low = mid + 1.
3. Termination: The loop stops when low > high. By then, the variable tracking the first bad version (badVersion) contains the correct result.

Code:

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

class Solution {
public:
    int firstBadVersion(int n) {
        // Initialize the search range
        int low = 1;          // The lowest version to check
        int high = n;         // The highest version to check
        int badVersion = -1;  // Variable to store the first bad version, default to -1
        
        // Perform binary search
        while (low <= high) {
            // Calculate the middle point of the current range
            int mid = low + (high - low) / 2;
            
            // Check if the current version is bad using the API
            if (isBadVersion(mid) == true) {
                // If it's bad, record it as a candidate for the first bad version
                badVersion = mid;
                // Move the search to the left (earlier versions) to find the first bad one
                high = mid - 1;
            } else {
                // If it's not bad, move the search to the right (later versions)
                low = mid + 1;
            }
        }
        
        // Return the first bad version found
        return badVersion;
    }
};

Complexity Analysis:

• Time Complexity: O(log n)
  • In each iteration, we reduce the search range by half using binary search.
• Space Complexity: O(1)