이진 탐색 ( + 하한 lower_bound, 상한upper_bound )

이진 탐색 

• 정렬되어 있는 데이터를 두 부분으로 나누며 값을 탐색하는 알고리즘
  • 비슷하게 분할하는 알고리즘으로 분할정복이 있다. 하지만 분할정복은 문제를 부분적으로 해결하는 알고리즘으로 탐색이 목적이 아니다. 
• 이진탐색은 '수가 존재하는지'  빠르게 알아낼 수 있다. 
• 단 중복원소가 있을 때 가장 왼쪽의 원소의 위치를 반환하는 방법과, 가장 오른쪽 원소의 위치를 반환하는 방법이 있다. 

 

기본적인 메커니즘

1. 탐색 범위 내[low ~ high]의 배열의 중간 인덱스[(low + high)/2]를 구한다. 
2. 중간 인덱스 값과 key 값을 비교한다. (key는 탐색하고자 하는 값)
3. key 값이 중간 값보다 작다면 왼쪽 부분을, key 값이 중간 보다 크다면 오른쪽 부분을 탐색한다.
   
   1. 이 과정을 반복하며 key 값이 있을 수 있는 범위를 줄여나간다. 
   2. 왼쪽 탐색 시 범위 수정: high = mid - 1 
   3. 오른쪽 탐색 시 범위 수정: low = mid + 1
4. key 값이 중간 인덱스 값과 같다면 해당 인덱스를 반환하고 종료

 

구현

    static int binary_search(int key) {
        int low = 0;
        int high = arr.length-1;
        
        while(low <= high) {
            int mid = (low+high)/2;
            if(key == arr[mid]) {
                return mid;
            }else if(key < arr[mid]){
                high = mid - 1;
            }else {
                low = mid + 1;
            }
        }
        
        // key가 없다. 
        return -1;
    }

 

 

중복 key 처리 

이진 검색해서 중복된 Key가 있을때, upper_bound, lower_bound를 알아야 한다. 

 

upper_bound(하한)

찾고자 하는 값 이상의 값을 처음으로 만나는 위치

 

lower_bound(상한)

찾고자 하는 값 초과한 값을 처음 만나는 위치

 

중복 원소에 대한 길이 = (상한 - 하한)  

만약 원소가 존재하지 않는다면 상한과 하한 모두 같은 인덱스를 가리키고 있을 것이기에 0이 되므로 이 또한 존재하지 않는 원소를 찾으려 할 경우의 예외 또한 안전하다.

 

 

위 그림에서 3의 lower bound는 4번째, upper bound는 7번째가 된다. 

 

 

중복 원소가 있는 이진 탐색 메커니즘

구간 내의 중앙 위치의 값을 기준으로 key 값과 비교를 한 뒤, 상한선(hi)을 내릴 것인지, 하한선(lo)을 올릴 것인지를 결정

 

 

 

 

 - (20.4.29.) 구현하는데 헷갈렸던 점

1) key </<= mid값 일 때, high를 줄이는 것 

반대는, low를 줄이는 것이다.

즉, mid값을 '예상 key값'으로 이해하면,, 예상 키값이 키보다 크면, high를 줄여 예상 키를 줄인다. 

예상 키값이 키보다 작다면, low를 키워 예상 키를 증가시킨다. 

반대로 high, low를 처리해서 값이 이상하게 나왔다. 

 

2) 만약 범위에 속하는 key가 존재하지 않는 경우도 주의하기 

key값이 존재하지 않으면,

 - 배열 길이 값(범위 초과)이 리턴되거나 ( lower + upper )

 - key보다 큰 값의 위치가 리턴된다. 이상을 찾는 lower의미가 달라짐 (lower bound)

   따라서, 배열[key] 값과 배열[리턴된 위치의 값]이 일치하는지 확인하여 lower_bound가 제대로 작동하는지 알 수 있다. 

 

 

    /*
     *  key이상 값이 처음으로 나오는 index 구하기 
     *  key가 모든 값보다 크다면 배열 길이가 리턴. 따라서, high 초기화가 기본 이진 탐색과 다르다. 
     */
    static int lower_bound_bs(int key) {
        int low = 0 ;
        int high = arr.length;
        
        while(low < high) {
            int mid = (low+high)/2;
            if(key <= arr[mid]) {
                // 처음으로 key와 동일하거나 이상을 찾아야 하기 때문에 = 포함하여 범위를 줄인다.  
                high = mid;
            }else {
                // mid값은 key보다 작기 때문에 절대 포함되지 않는다. 따라서, mid+1로 범위 줄인다. 
                low = mid + 1;
            }
        }
        
        // low와 high동일해서 아무거나 리턴해도된다. 
        return low;
    }
    
    /*
     *  key보다 큰 값이 처음으로 나오는 index 구하기 
     *  key가 모든 값보다 크면 배열 길이 리턴 
     */
    static int upper_bound_ps(int key) {
        int low = 0;
        int high = arr.length;
        
        while(low < high) {
            int mid = (low+high)/2;
            if(key < arr[mid]) {
                // 처음으로 key보다 큰 값을 찾아야 하기 때문에 = 제외하여 범위를 줄인다. 
                high = mid;
            }else {
                // mid값은 key보다 작기 때문에 절대 포함되지 않는다. 따라서, mid+1로 범위 줄인다. 
                low = mid + 1;
            }
        }
        
        // low와 high동일해서 아무거나 리턴해도된다.
        return low;
    }

 

 

 

 

 

 

참고 및 출처

https://jackpot53.tistory.com/33?category=715474

http://bajamircea.github.io/coding/cpp/2018/08/09/lower-bound.html

https://st-lab.tistory.com/267