Problem Statement

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 will return whether version is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.

Solution Explanation

Given a integer 'n', we have to find out the first bad version, a integer 'i' before 'n' where isBadVersion returns true and false for i-1.

This is basically a binary search problem, each time you check if mid is the bad version between 0 and n, keep updating the start and end values. When you exit, check if mid is the bad version and return it, if not return mid+1.

Here's how the code looks like in Java,

    
    public class FirstBadVersion extends VersionControl {
    public int firstBadVersion(int n) {
        //if(isBadVersion(n)) return n;
        int i=0, j =n, mid=0;
        while(i<=j){
            mid = i + (j-i) / 2;
            if(!isBadVersion(mid)) i = mid+1;
            else j = mid-1;
        }
        if(!isBadVersion(mid)) return mid+1;
        return mid;
    }
}

This assumes the VersionControl class provides the method isBadVersion().

Time Complexity

We just do a binary search between 0 and n, so it is O(log n) and space complexity is O(1).