First Bad Version: Binary Search and Return Low

First Thoughts: interesting point about this problem is that if there is one bad version in the list, all following versions are bad -> can't just end function if one bad solution found (need to find where it originated). The first one is what we are interested in. The question seems much like a typical binary search problem, except that the lowest one should be returned by the end (the first one to be bad)

My Solution:

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

Every time, we cut the list in half and check the middle. If the middle is bad, means the origin is still at the lower half -> adjust high point to mid, vice versa (except when we set low point, set to one more than just mid, because already checked mid was bad). If it keeps adjusting, at the end it means that the leftmost version was the original bad one.

Catch Point

1. Lowest point ends up being the first bad version at the end of elimination process.

2. Finding one bad version is not enough -> need to adjust low and high point accordingly.

3. Adding one check (if first one is bad or there is only one version in list) can greatly reduce actual runtime (although time complexity will not change)