[LeetCode 278.] First Bad Version (Java)

문제

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

n개의 버전[1, 2, ..., n]이 있고 첫 번째 불량 버전을 찾은 그 이후 다음 버전은 모두 불량이다.

버전이 잘못된지 여부를 반환하는 API bool isBadVersion(version) 이 제공된다.

API에 대한 호출 수를 최소화하여 첫 번째 불량 버전을 찾는 기능을 구현해야 된다.

풀이

1. 전체 버전에서 첫 번째와 마지막 버전을 지정한다.
2. 가장 중앙 버전의 불량여부를 확인한다.
3. 중앙 버전이 불량인 경우,
   1. 해당 제품의 이전 제품이 정상인 경우, 중앙값 리턴,
   2. 이전 제품도 불량이라면, 중앙제품 이전 제품을 마지막 버전으로 설정한다.
4. 중앙 버전이 정상인 경우 중앙 다음 제품을 최초 제품으로 설정한다.

Java Code

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

public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        if(n==1) return 1;        
        
        int begin = 1;
        int end = n;
        int mid = (end - begin) / 2 + begin;
        
        while(true){
            if(isBadVersion(mid)){
                
                if(!isBadVersion(mid-1)){
                    return mid;
                } else {
                    end = mid-1;
                    mid = (end-begin) / 2 + begin;
                }
                
            } else {
                
                begin = mid+1;
                mid = (end-begin) / 2 + begin;
                
            }
        }
    }
}