278. First Bad Version

Description

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 one, all the following versions are also bad. Given an API bool isBadVersion(int version), which returns whether a version is bad, your task is to find the first bad version in the sequence of versions.

You need to minimize the number of calls to the isBadVersion API.

Intuition

The problem can be reduced to a classic binary search scenario where you are trying to find the first occurrence of a bad version in a sequence. By narrowing down the search space through binary search, we can efficiently find the first bad version with minimal API calls.

The idea is to repeatedly divide the search space in half, which allows us to focus only on the relevant portion of the sequence that could contain the first bad version.

Approach

1. Binary Search Setup: Initialize two pointers, left at 1 (the first version) and right at n (the last version).
2. Midpoint Calculation: In each iteration, calculate the midpoint of the current range.
3. Check Midpoint: - If the version at mid is bad, then the first bad version must be at mid or before it, so move the right pointer to mid. - If the version at mid is not bad, then the first bad version must be after mid, so move the left pointer to mid + 1.
4. Repeat until left equals right. At this point, left will be pointing to the first bad version.

Complexity

Time Complexity:

O(log n). The binary search algorithm reduces the search space by half each time, leading to a logarithmic time complexity relative to the number of versions n.

Space Complexity:

O(1). The algorithm only uses a constant amount of extra space for the pointers and midpoint calculation.

Code

C++

// Forward declaration of isBadVersion API.
// bool isBadVersion(int version);

class Solution {
public:
    int firstBadVersion(int n) {
        int left = 1, right = n;

        while (left < right) {
            int mid = left + (right - left) / 2;
            if (isBadVersion(mid)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }

        return left;
    }
};

Python

# The isBadVersion API is already defined for you.
# def isBadVersion(version: int) -> bool:

class Solution:
    def firstBadVersion(self, n: int) -> int:
        left, right = 1, n

        while left < right:
            mid = (left + right) // 2
            if isBadVersion(mid):
                right = mid
            else:
                left = mid + 1

        return left

Java

/* The isBadVersion API is defined in the parent class VersionControl.
   boolean isBadVersion(int version); */

public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        int left = 1, right = n;

        while (left < right) {
            int mid = left + (right - left) / 2;
            if (isBadVersion(mid)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }

        return left;
    }
}

JavaScript

/**
 * Definition for isBadVersion()
 * 
 * @param {integer} version number
 * @return {boolean} whether the version is bad
 * isBadVersion = function(version) {
 *     ...
 * };
 */

var solution = function(isBadVersion) {
    /**
     * @param {integer} n Total versions
     * @return {integer} The first bad version
     */
    return function(n) {
        let l = 1, r = n;

        while (l < r) {
            const mid = Math.floor((l + r) / 2);
            if (isBadVersion(mid)) r = mid;
            else l = mid + 1;
        }

        return l;
    };
};