278. First Bad Version

문제 설명

You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad.
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 returns whether version is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.

프로덕트 매니저인 당신은 새 제품을 개발하는 팀을 이끌고 있다. 불행히도, 제품 중 가장 최신 버전이 퀄리티 체크에 실패했다. 각자의 버전은 이전 버전을 토대로 개발되기 때문에, 불량 버전 이후의 모든 버전 역시 불량이 된다.
당신은 n개의 버전 [1,2,3, ... ,n] 을 가지고 있고 가장 최초의 불량 버전을 찾고 싶다.
버전의 불량 여부를 알려주는 bool isBadVersion(version) API가 주어진다. 함수를 삽입하고 최초 불량 버전을 찾아라. 단, API의 호출 횟수가 최소가 되어야 한다.

출력 예시

접근 방법

첫번째 시도

가장 먼저 떠오른 이분 탐색! 우선 중간 값 mid에서의 버전을 탐지 한 뒤, true라면 첫번째부터 mid-1까지의 중간 값을 판단, false라면 mid+1부터 마지막까지이 중간 값을 판단하는 방법 이용하기.

소스코드

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

class Solution {
public:
    int firstBadVersion(int n) { //1 2 3 4
        int answer=n;
        long long start = 0;
        long long end=n-1;
        while(start<=end){
            long long cur = (start+end)/2;
            if(isBadVersion(cur+1)){
                if(cur+1 < answer) answer = cur+1;
                end = cur-1;
            }
            else{
                start=cur+1;
            }
        }
        
        return answer;
        
    }
  
};

돌아보기

방법은 제대로 찾았지만 start,end 변수를 int형으로 선언해서 오버플로가 났다... 범위 확인 제대로 하기!