LeetCode 278. First Bad Version

문제 링크: leetcode.com/problems/first-bad-version/

First Bad Version - LeetCode

문제 요약: n 이 주어질때, 최초로 불량이 나는 n을 찾아라. isBadVersion(int n)이라는 메소드는 주어진다. 

만약 3이 불량(false)이면 3부터 n까지는 모드 불량, 즉 1~n 중에서 최초로 isBadVersion(n)이 false인 수를 찾는문제.

 

문제 접근: for문으로 1부터 순차적으로 돌면 timeout이 발생해서, binary search 로 풀었다. 주의할점은 int 범위를 신경써서 해야 풀린다. (이것땜에 고생함)

/* 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;
        return recursion(n, 1, n);
    }
    
    public int recursion(int n, int minRange, int maxRange) {
        if (n == 1) return n;

        boolean badVersion = this.isBadVersion(n);
        if(badVersion && !this.isBadVersion(n-1)) return n;

        if (badVersion) {
            int nextMaxRange = n;
            n = minRange + (maxRange - minRange)/2;
            return this.recursion(n, minRange, nextMaxRange);
        } else {
            int nextMinRange = n;
            n = n + (maxRange - n)/2;
            return this.recursion(n, nextMinRange, maxRange);
        }
    }
}

참고: a,b 의 중간값을 구할때 (a+b)/2 보단, a + (b-a)/2 로 하자..