LeetCode //C - 278. First Bad Version

278. First Bad Version

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

Constraints:

• $1<=bad<=n<=2^{31}-1$

From: LeetCode
Link: 278. First Bad Version

Solution:

Ideas:

1. Initialize two pointers: Set left to 1 (the first version) and right to n (the last version).

2. Iterate until the search space is exhausted: Continue until left is less than or equal to right.

3. Check the middle version: Calculate the midpoint mid using (left + right) / 2 to avoid potential overflow.

4. Evaluate the mid version using isBadVersion(mid):

• If true, it indicates that mid and possibly earlier versions could be bad. Set right to mid - 1 to focus on the left half (earlier versions).
• If false, it means versions prior to mid are all good, so set left to mid + 1 to concentrate on the right half (later versions).

5. Determine the first bad version: When the loop ends, left will be the smallest version number that returned true for isBadVersion(), signifying the first bad version.

Code:

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

int firstBadVersion(int n) {
    int left = 1, right = n;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (isBadVersion(mid)) {
            right = mid; // Look on the left side, including mid
        } else {
            left = mid + 1; // Look on the right side, excluding mid
        }
    }
    return left; // When left == right, we've found the first bad version
}