이진탐색

이진탐색(Binary Search)

정렬된 배열(수열)에서 원하는 값을 효율적으로 찾는 탐색 알고리즘
한번의 탐색으로 탐색 범위를 반으로 줄일 수 있어 이진탐색이라 불린다.

시간복잡도

O(log N) 로 탐색범위가 커질 수록 효율적이다.

구현

배열에서 특정 값을 찾아내는 이진탐색 구현

public int binarySearch(int[] arr,int n){
        int start = 0; //탐색 시작부분
        int end = arr.length - 1; //탐색 마지막부분

        while(start <= end) {
            int mid = (start + end) / 2;// 탐색구간의 중간
            if(arr[mid] == n){
                return mid; //n을 찾은경우 n의 index를 반환.
            }

            if(arr[mid] > n){
                //찾고자하는 값이 중간값보다 큰 경우,
                //start부터 mid까지 탐색할 필요가 없어져 탐색범위가 반으로 줄어든다.
                start = mid + 1;
            }else{
                //찾고자하는 값이 중간값보다 작은 경우,
                //mid부터 end까지 탐색할 필요가 없어져 탐색범위가 반으로 줄어든다.
                end = mid - 1;
            }
        }
        /*탐색이 1회 진행될때마다, start가 증가하거나 end는 감소하므로
        탐색이 계속되면 start가 end보다 커지는 상황이 발생하고 
        해당 경우는 배열에 원하는 값이 존재하지 않음을 의미한다.*/
        return -1; //배열에 n이 없는 경우 -1을 반환.
    }

배열에서 특정 조건에 부합하는 범위를 구하는 이진탐색

숫자 카드 2 문제처럼, 값이 중복될 수 있는 배열에서 특정 값이 몇개 포함되어 있는지 찾을때도 이진탐색을 사용할 수 있다.
이때는 하한, 상한의 개념을 알아야 한다.

하한(Lower bound)

정렬된 배열에서 특정 값 이상이 처음으로 나타나는 위치

상한(Upper bound)

정렬된 배열에서 특정 값을 초과하는 값이 처음으로 나타나는 위치

즉, 배열에서 찾고자하는 값의 하한과 상한을 찾으면 배열에 특정 값이 몇개 포함되어 있는지 알 수 있다.

상한/하한 찾는 방법

public int lowerBound(int[] arr, int n){
        int start = 0; //하한이 될 수 있는 시작 점.
        int end = arr.length; //하한이 될 수 있는 마지막 점.
        //상한 혹은 하한을 찾을때,
        //start 와 end는 하(상)한의 가능한 모든 범위를 설정해줘야 한다.
        
        while(start < end){ //start 와 end가 같아질때까지 반복
            int mid = (start + end) / 2;

            if(arr[mid] >= n){
                //찾고자하는 값이 중간값보다 크거나 같은경우,
                //즉, 탐색범위가 start ~ mid 로 축소된다.
                end = mid;
            }else{
                //찾고자하는 값이 중간값보다 작은 경우,
                //즉, 탐색범위가 (mid + 1) ~ end 로 축소된다.
                start = mid + 1;
            }
        }
        return start;
    }

    public int upperBound(int[] arr, int n){
        int start = 0;
        int end = arr.length;

        while(start < end){
            int mid = start + (end - start) / 2;

            if(arr[mid] > n){
                //찾고자하는 값이 중간값보다 큰 경우,
                end = mid;
            }else{
                //찾고자하는 값이 중간값보다 작거나 같은 경우,
                start = mid + 1;
            }
        }
        return end;
    }