Binary search on Answer

Binary search Intro
From the intro, we already know what is the binary search and how it works. Where we discussed how to find a position of a given target value.

Sometimes we don't know what is the target value, but we know the range where the target value can exist. So, we can apply the binary search for the answer itself.


Let's talk about this problem.
In this problem, we are given a range, in this range more than one answer can exist, but we have to find the first value.

Hence we don't know the target value, at the same time we have to return the first value so we can search for the value with the same approach, after the end of the search answer can be found at the left variable.

Simple implementation:

int firstBadVersion(int n) {

        int l = 1, r = n;

        while(l < r){

            int mid = (l+r)/2;

            if(isBadVersion(mid)) r = mid;

            else l = mid+1;

        }

        return l;

}

Similar questions,
Guess
Divide Two Integers