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

The most efficient way to solve this problem is using Binary Search. Since all versions after the first bad version are also bad, we can leverage the sorted nature of the "badness" to perform a binary search.

1. Initialization: Set left = 1 and right = n. This defines 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 the first bad version is either mid itself or somewhere before it. Therefore, we update right = mid - 1.
     • If false, this means the first bad version is somewhere after mid. We update left = mid + 1.
3. Return: After the loop finishes, left will point to the first bad version.

Code (C#)

public 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;
    }

    // This is a placeholder for the actual isBadVersion API.  You would replace this with the provided API.
    bool IsBadVersion(int version) {
        // Replace this with the actual implementation of isBadVersion
        // This is just an example.
        return version >= 4; 
    }
}

Complexity

• Time Complexity: O(log n). Binary search reduces the search space by half in each iteration.
• Space Complexity: O(1). The algorithm uses a constant amount of extra space.