First Bad Version

풀이

또또또 문제 설명 아주그냥 뭐같은 문제임

그냥 핵심은 이진탐색하라는거임

you should minimize the number of calls to the API

라고 함

• 가장 최소의 bad version을 1~n사이의 값 중 찾아야함
• bad version은 isBadVersion메서드의 호출을 통해 해당 숫자가 bad version인지 아닌지 알 수 있음

class Solution {
public:

    int firstBadVersion(int n) {

        long l = 1;
        long mid = 0;
        
        while(l <= n)
        {
            mid = (l + n) / 2;

            if(isBadVersion(mid))
            {
                n = mid - 1;
            }
            else
            {
                l = mid + 1;
            }
        }

        return l;

    }
};

중요한건 l을 리턴한다는거임

왜? l을 리턴함? mid리턴해야하는거 아님??

ㄴㄴ
mid는 단순히 해당 수가 bad version인지 아닌지 판가름 하는 용도로 이 풀이에서는 사용중임

n은 version중 bad version이 발견되면,
바로 bad version의 상한선이 됨

l은 version중 bad version에 관계없이
모든 수의 하한선이 됨

따라서 상한선을 계속 낮추면서 하한선을 올리면서
하한선이 상한선을 추월하는 상황이 바로 bad version의 최하값이 되는거임