278. First Bad Version

LeetCode Questions No. 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.

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

To find the first bad version, we can use binary search. We can start by checking the middle version and based on whether it is bad or not, we can discard half of the remaining versions. We can keep doing this until we find the first bad version.

Let's see the implementation of the function:-
The implementation of the firstBadVersion function in Java:

	
 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;
        } else {
            left = mid + 1;
        }
    }
    return left;
}
    

In this implementation, we use the same binary search approach as the previous implementation. We initialize the left and right pointers to the first and last versions respectively. We then use a while loop to keep narrowing down the range of versions to check.
We calculate the mid version and check whether it is bad or not using the isBadVersion method.
If it is bad, we discard the right half of the remaining versions and search in the left half.
If it is not bad, we discard the left half and search in the right half.
We keep doing this until we find the first bad version, which is the left pointer.
The time complexity of this algorithm is O(log n) and the space complexity is O(1), since we are only using a constant amount of extra space for the left and right pointers.

Why is O(log n) the time complexity of this algorithm

The time complexity of this algorithm is O(log n) because we are using binary search to find the first bad version.
In each iteration of the while loop, we cut the remaining versions to search in half, so the size of the problem is reduced by a factor of 2.
This means that the number of iterations required to find the first bad version is proportional to the logarithm of the number of versions n.
Specifically, the number of iterations required is ceil(log2(n)) (the base-2 logarithm of n rounded up to the nearest integer).
Since each iteration involves one call to the isBadVersion API, the total number of calls to the API is also proportional to the logarithm of n.
Therefore, the time complexity of this algorithm is O(log n).
Compared to a linear search, which would require O(n) calls to the API to find the first bad version, using binary search significantly reduces the number of calls and the time complexity of the algorithm.

/* 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 start = 1;
        int end = n;
        int result = 1;
        while(start <= end){
            int mid = start + (end-start)/2;
            if(isBadVersion(mid)){
                end = mid - 1;
                result = mid;
            }else
                start = mid + 1;
            }
        return result;
    }
}