First Bad Version

Problem Statement

LeetCode-278: 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.

Approach

Given the versions are already sorted [1, 2, ..., n] the given problem is a variation of Binary Search algorithm. We can use the binary search algorithm to find the first bad version.

The idea is to keep track of the start and end pointers. We will keep moving the pointers based on the result of the isBadVersion function.

If the mid version is a bad version, we need to move to the left side of the mid version to find the first bad version. Otherwise, we need to move to the right side of the mid version. Also, as the current mid could be the first bad version, we need to keep track of the first bad version found so far.

Implementation

Following is the implementation of the above approach.

public int firstBadVersion(int n) {
    int start = 1;
    int end = n;
    int firstBad = 1;
    while(start <= end){
        int mid = start + ((end-start) >> 1);
        if(isBadVersion(mid)){
            firstBad = mid;
            end = mid-1;
        }else{
            start = mid + 1;
        }
    }
    return firstBad;
}

Complexity Analysis

The time complexity for the above approach is \(O(log\ n)\) as we are using the binary search algorithm to find the first bad version. The space complexity is \(O(1)\) as we are using only a constant amount of space.