Marc Lester Tan

This easy LC problem was asked in one of my past interviews (Facebook) which I think I didn’t really answered very well.

public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        if(n == 0) return 0;
        
        int low = 1;
        int high = n;
        
        while(low <= high){
            int mid = low + (high-low)/2;
                
            if(isBadVersion(mid)) {
                high = mid - 1; 
            }else {
                low = mid + 1;
            }            
        }
        
        return low;
    }
}

It uses binary search with overflow protection to find the first bad version. An improved version of this could check for the mid - 1 also so we can immediately verify if the mid is indeed the first bad version. But this could also mean a potential extra call to isBadVersion which is violating the requirement of the problem of minimizing the number of calls to this API.

Runtime: 10 ms, faster than 99.48% of Java online submissions for First Bad Version.
Memory Usage: 33.3 MB, less than 100.00% of Java online submissions for First Bad Version.