First Bad Version easy

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.

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

Steps and Explanation

This problem is perfectly suited for a binary search approach. Since all versions after the first bad version are also bad, we can leverage the sorted nature of the "badness" to efficiently find the first bad version.

1. Initialization: Start with left = 1 and right = n. This defines our search space.

2. Iteration: While left <= right:

   • Calculate the mid point: mid = left + (right - left) / 2. This prevents potential integer overflow.
   • Call isBadVersion(mid):
     • If isBadVersion(mid) is true, it means the bad version is at or before mid. We update right = mid - 1 to search in the left half.
     • If isBadVersion(mid) is false, it means the bad version is after mid. We update left = mid + 1 to search in the right half.

3. Return: After the loop, left will point to the first bad version.

The binary search approach dramatically reduces the number of calls to isBadVersion compared to a linear search. Instead of potentially checking every version, it halves the search space with each iteration.

Code (C++)

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

class Solution {
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 - 1;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
};

Complexity

• Time Complexity: O(log n). The binary search algorithm reduces the search space by half in each iteration.
• Space Complexity: O(1). The algorithm uses a constant amount of extra space. We only need a few integer variables.