278. First Bad Version

문제 파악 및 재정의

n개의 버전이 주어지고 isBadVersion API가 제공된다.

첫 번째 불량 버전을 찾는 기능을 구현하며, API의 사용 횟수를 최소화 하라.

 

자료구조 및 알고리즘 선택

BinarySearch -> start와 end를 옮겨가며 mid의 위치를 조정하여 찾는 방식

구현

public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        int answer = 0;
        int start = 0;
        int mid = n/2;
        int end = n;

        if(n == 1) return 1;

        // 탈출 조건
        
        while(true) {
            if(end == start) {
                answer = start;
                break;
            }
            if(isBadVersion(mid)) {
                end = mid;
            }else{
                start = mid+1;
            }
            mid = (start + end) / 2;
        }
        return answer;
    }
}

회고

못 품

BinarySearch 문제를 많이 다뤄 mid의 위치 조정하는 그림이 잘 그려지도록 해보자.

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

public class Solution extends VersionControl {

    public int firstBadVersion(int n) {
        int low = 0;
        int high = n;

        while(low<=high){
            int mid = low + (high-low)/2;
            if(isBadVersion(mid)==true && isBadVersion(mid-1)==false)   return mid;
            else if(isBadVersion(mid)==false ) low = mid+1;
            else high= mid;
        }     
        return -1;
    }
}