Problem

https://leetcode.com/problems/first-bad-version/description/?envType=problem-list-v2&envId=rab78cw1

grind 75의 easy 문제다.

Solution

1부터 n 사이의 버전에서 퀄리티 체크에서 최초로 bad 판정을 받은 버전을 반환하는 문제다.

git 형상 관리를 떠올려볼까? 한번 코드에서 에러가 나면 이후 형상들은 전부 에러가 발생한다.
그러면 현재가 isBadVersion(?)이라면? 내 뒤는 bad일게 뻔하고 내 앞도 bad일 가능성이 있다.
현재가 bad가 아니라면 미래의 version들 중에서 bad를 찾아야 한다.

그림을 그려보니 ?를 기준으로 익숙한 이분법 그림이 보인다. 이 문제는 투 포인터를 활용한 이분탐색으로 풀어야겠다.

Code

정답을 맞추고 나면 사실 minBadVer 변수는 필요없이 그냥 right을 리턴하면 된다는 것을 깨닫는다.
하지만 개념을 확실히 익히기 위해서 조금의 성능 차이는 그냥 넘어갔다.

public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        // 투 포인터에 이분탐색으로 진행해야 한다. 
        int left = 0;
        int right = n;
        int minBadVer = n;

        while (left <= right) {
            int mid = left + (right - left) / 2;

            if (isBadVersion(mid)) {
                // 지금 버전은 나쁘다. 
                // 지금 버전이 딱 나쁜걸까 아니면 내 이전 버전이 나쁜걸까?
                minBadVer = Math.min(minBadVer, mid);
                // 내 왼쪽 버전이 더 나쁜거 같다. 
                right = mid - 1;

            } else {
                // 지금 버전은 나쁘지 않다. 내 오른쪽 버전이 나쁜거 같다.
                left = mid + 1;
            }
        }

        return minBadVer;
    }
}