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

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

First Bad Version - LeetCode

/* 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;
        if(n==2){
            if(super.isBadVersion(n-1)){
                return 1;
            }else{
                return 2;
            }
        }
        
        //중간값을 호출해서 값을 찾는다. 시간복잡도 logn2
        boolean check = false;
        int mid = (int)Math.ceil(n/2); //4/2 = 2
        check = super.isBadVersion(mid);
        
        if(check){//고장난게 맞아
            int previousNum = mid-1;//이전 값도 고장났니?
            check = super.isBadVersion(previousNum);
            if(check){//어 이전 값도 고장났어
                return previousNum;
            }else{
                return mid;//꺅 정답 찾음
            }
        }else{//정상이야 그럼 오른쪽으로 계속해서 찾아본다
            int nextNum = mid +1;//다음 값은? 고장났어?
            check = super.isBadVersion(nextNum);
            if(check){//어 고장났어
                return nextNum;// 꺅 정답 찾음
            }else{
                nextNum = nextNum +1;//아니 다음으로 넘어가야할거같아
            }
            
        }

    System.out.println("end");
        return 0;
    }
}

이렇게 하다가 

이거.. 점점 길어지겠구나 하고 답지 검색함.

 

이진 탐색 기법을 사용하면된다고하네

 

public int firstBadVersion(int n) {

    int start = 1;
    int end = n;

    while(start <= end){
        int mid = start + (end-start)/2;
        if(isBadVersion(mid)){
            end = mid-1;
        }else{
            start = mid+1;
        }
    }
    return start;
}

이렇게 짧아진다고?

 

보니까

처음~~~~~중간~~~~~끝의 구간을 반반 자르는 개념이다.

 

찾는 값 > 중간값 :

                 중간~~~~~끝  을

                 시작~~~~~끝 으로 바꾸고

 

찾는 값 < 중간값 :

처음~~~~~중간

처음~~~~~끝  으로 바꾸면 된다.

 

 

 

위에 코드 보고 이해가 잘안가서

https://cjh5414.github.io/binary-search/

이진 탐색(Binary Search) 알고리즘 개념 이해 및 추가 예제

여기를 통해서 범위를 반으로 줄인다는 것을 이해했다.

 

반복문 이용

int BSearch(int arr[], int target) {
    int low = 0;
    int high = arr.length - 1;
    int mid;

    while(low <= high) {
        mid = (low + high) / 2;

        if (arr[mid] == target)
            return mid;
        else if (arr[mid] > target)
            high = mid - 1;
        else
            low = mid + 1;
    }
    return -1;
}

 

 

재귀함수 이용

int BSearchRecursive(int arr[], int target, int low, int high) {
    if (low > high)
        return -1;

    int mid = (low + high) / 2;
    if (arr[mid] == target)
        return mid;
    else if (arr[mid] > target)
        return BSearchRecursive(arr, target, low, mid-1);
    else
        return BSearchRecursive(arr, target, mid+1, high);
}