[leetcode 75] 278. First Bad Version

문제해석

n이 주어졌을 경우 1.2.3...n 까지의 버전별 제품이 존재하는데 만약 최초로 불량버전이 존재하는 버전 이후로 모든 버전은 불량일 때

최초 불량제품의 버전을 찾기

 

정답 예

public int firstBadVersion(int n) {
    if (n == 1) {
        return 1;
    }

    if (isBadVersion(n) && !isBadVersion(n-1)) {
        return n;
    }

    int start = 1;
    int end = n;
    int mid;

    // bad version 의 시작 발견시 종료
    while(end > start) {

        // 원래는 (start + end) / 2 인데 start + end를 하면 int 형 값의 범위보다 커져서 범위를 초과하지 않게 계산식 변경
        mid = start + (end - start) / 2;


        if (isBadVersion(mid)) { // bad version 발견시 더 이전 버전의 bad version이 있는지 찾는다.
            end = mid;
        } else { // bad version이 아닐시 이후 버젼의 bad version이 있는지 찾는다.
            // +1 을 넣어주어 bad version이 아닌 버전이 기존 bad version의 바로 앞전 값인지 체크할 수 있도록 유도
            start = mid + 1;
        }
    }
    return end;
}