10. Binary Search(이진 탐색)

 

이진 탐색은 범위를 반으로 나눠가며 찾는 것이다.

선형 탐색보다 훨씬 빠르게 타겟을 찾을 수 있다. 

 

시간 복잡도는 NlogN이다 

 

주의할 점은, 이진 탐색에서 m의 왼쪽에 m보다 작은 요소가, 오른쪽에 m보다 큰 요소가 있는 걸 보장하기 위해, 이진 탐색 전에 배열은 반드시 정렬되어 있어야 한다. 

 

예를 들어서, 9개의 요소를 가진 배열 arr가 있다고 가정하자.

1

2

3

4

5

6

7

8

9

이렇게 있을 때, 3을 찾는다고 하자.

 

일단 전체 arr[0] ~arr[8] 중 중간 요소가 3인지 확인한다.

타겟은 3보다 5가 크므로 5보다 아래에 있다는 소리이다.

 

그럼 다시 arr[0] ~ arr[3] 을 찾아본다.

중간((0+3)/2)은 arr[1] == 2 이다. 

타겟 보다 작으므로 오른쪽에 있다는 소리다.

 

그럼 다시 arr[2] ~ arr[3] 을 찾아본다

중간((2+3)/2 = 2) 인 arr[2]을 보니 3이다. 찾았다!

 

이렇게 탐색 범위를 반으로 쪼개가면서 찾는 것이 이진 탐색이다. 

 

간단하게 코드로 표현하면 다음과 같다

int arr[9] = {1, 2, 3, 4, 5, 6, 7, 8, 9};

int binarySearch(int s, int e, int target){
    int m;
    while(s<=e){
        m = (s+e)/2;
        if(arr[m] == target) return m+1;
        if(arr[m]>target) e=m-1;
        else s = m+1;
    }
    if(s>e) return 0;
}

 

만약 배열에 중복되는 값이 있다면, 이 중에 가장 후자, 전자를 뽑아낼 수도 있다.

UpperBound Binary Search, LowerBound Binary Search 등으로 부르는데, C++에는 vector에 lower_bound(), upper_bound() 등의 이미 정의된 라이브러리 함수를 사용할 수 있다.

 

C를 통해 upperbound, lowerbound search를 구현해보면 다음과 같다. 

 

Upper Bound Binary Search

// upper_bound binary search
int BinarySearchUpper(int s, int e, int d){
    int m, sol = -1;
    while(s<=e){
        m = (s+e)/2;
        if(narr[m] == d){
            sol = m; // 답의 후보
            s = m+1; // 오른쪽으로 가봄
        }else if(narr[m] > d){
            e = m-1; // 왼쪽을 탐색한다
        }else{
            s = m+1;	// 오른쪽을 탐색한다
        }
    }
    return sol;
}

Lower Bound Binary Search

// lower_bound binary search
int BinarySearchLower(int s, int e, int d){
    int m, sol = -1;
    while(s<=e){
        m = (s+e)/2;
        if(narr[m] == d){
            sol = m; // 답의 후보
            e = m-1; // 왼쪽으로 가봄
            //return m;
        }else if(narr[m] > d){
            e = m-1;
        }else{
            s = m+1;
        }
    }
    return sol;
}

 

기본 이진 탐색과 다른 점은, 타겟을 찾았어도, 리턴하지 않고 왼쪽, 오른쪽으로 탐색을 계속한다는 것이다.