// The API isBadVersion is defined for you.
// bool isBadVersion(int version);

class Solution {
public:
    int firstBadVersion(int n) {
        int lower = 1, upper = n;
        int mid=0;
        while(lower<upper)
        {
            mid = lower+(upper-lower)/2;
            if(!isBadVersion(mid)) // 만역 버전이 bad가 아니면
            {
                lower = mid + 1; // only one call to API
            }
            else // 만역 버전이 bad이면
            {
                upper = mid;
            }
        }
        return lower; // because there will alway be a bad version, return lower here

    }
};