Leetcode - First Bad Version

문제

https://leetcode.com/problems/first-bad-version/description/

First Bad Version - LeetCode

 

 

풀이

먼저 n이 2^31 - 1 이하이기 때문에 오버플로우에 주의해야 한다.

 

[left, right] 구간은 badVersion이 가능한 구간을 의미한다.

 

따라서 isBadVersion = true 일 때 right = version 할당하고 false 일 때 left를 version + 1로 할당해야 한다.

 

left가 right를 침범하게 되면 더 이상 badVersion 범위를 좁힐 수 없기 때문에 left를 리턴한다.

/* The isBadVersion API is defined in the parent class VersionControl.
      boolean isBadVersion(int version); */

public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        // bad 버전이 나오면 그 뒤는 모두 bad 버전
        int left = 1;
        int right = n;
        
        while (left < right) {
            int version = left + (right - left) / 2;
        
            if (isBadVersion(version)) {
                right = version;
            } else {
                left = version + 1;
            }
        }
        
        return left;
    }
}