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 the failure of the quality check. You are given an API boolean isBadVersion(version) which will return 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
Explanation:
The first bad version is 1.

Steps and Explanation

This problem is ideally solved using Binary Search. Since all versions after the first bad version are also bad, we can efficiently eliminate half the search space with each comparison.

1. Initialization: Start with left = 1 and right = n. These represent the lower and upper bounds of the search space.

2. Iteration: While left <= right:

   • Calculate the middle point: mid = left + (right - left) / 2. This prevents potential integer overflow.
   • Check if isBadVersion(mid) is true:
     • If true, this means mid could be the first bad version, or it's after the first bad version. We need to search in the left half: right = mid - 1.
     • If false, this means mid is a good version, so the first bad version must be in the right half: left = mid + 1.

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

Code (Java)

public class Solution extends VersionControl {
    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;
    }
}

Note: The VersionControl class and isBadVersion method are provided by LeetCode. You don't need to implement them. They are part of the problem's interface.

Complexity

• Time Complexity: O(log n). Binary search reduces the search space by half in each step.
• Space Complexity: O(1). Constant extra space is used. The algorithm's space usage is independent of the input size.