이분탐색 (binary search)

이분탐색 (binary search)

주제에 들어가기 앞서, 자주 일어나는 상황을 하나 가정해 보겠습니다.

길이 n짜리 배열이 있습니다. 이 배열안에는 정수가 오름차순으로 정렬되어 저장되어 있습니다. 이때, 특정한 정수값 x가 저장된 위치(인덱스)를 찾고 싶습니다. 어떻게 위치를 구할까요?

1. 앞에서 부터 탐색

가장 쉽게 생각할수 있는 방법은 앞에서부터 순차적으로 찾아나가는 것입니다.

int o[n]; <- 길이 n짜리 배열
for(int i = 0; i < n; i++){
    if(o[i] == x){
        printf("finding position is : %d\n", i);
    }
}

하지만 앞에서 부터 찾아가는게 아니라, 임의의 위치 에서 찾아나가면 어떻게 될까요?

2. 임의 위치부터 탐색

예시를 들어 보겠습니다.

  0   1   2   3   4   5   6   7   8   9     : index
+---+---+---+---+---+---+---+---+---+---+
| 1 | 2 | 2 | 3 | 4 | 4 | 5 | 7 | 9 | 9 |   : value
+---+---+---+---+---+---+---+---+---+---+

이 배열에서 value가 ‘‘3'’인 index를 찾아보겠습니다. 제가 임의대로 index를 골라서 찾아보겠습니다.

1. index 7 선택 : value가 7 입니다. 저희가 찾고자 하는 값보다 더 크네요. 여기서 우리는 추가적인 정보를 알게 됩니다. 바로 index가 7보다 큰 곳은 무조건 value가 7 보다 크다는 것 입니다. 그러니… index가 7 이상이면 value가 3보다 크게 됩니다. 따라서 index 8, 9 는 살펴볼 필요가 없습니다.

즉 [0, 1, 2, 3, 4, 5, 6] 인덱스 중에 원하는 위치가 있습니다.

1. index 2 선택 : value가 2 입니다. 3보다 작습니다. 자연스럽게 index 0, 1은 볼 필요가 없게 됩니다.

이제 후보군은 [3, 4, 5, 6] 이 됩니다.

1. index 6 선택 : value가 5 입니다. 3 보다 크네요. 후보군에서 index 6 만을 제거해줍니다.

[3, 4, 5] 가 남았습니다.

1. index 5 선택 : value가 4 입니다. 3 보다 큽니다. 그러니 후보군에서 제거해줍니다.

[3, 4] 가 남았습니다.

1. index 4 선택 : value가 4 입니다. 3 보다 큽니다. 그러니 후보군에서 제거해줍니다.

[3] 가 남았습니다.

1. index 3 선택 : value가 3 입니다.!!! 원하는 값을 찾았습니다. 정답은 index 3 였습니다!

여기까지 순서대로 따라오시면서 뭔가 답답하신 분들이 계실 겁니다. 따라 읽으시면서 속이 터졌길 바랍니다. 자… 뭐가 문제였을까요? 뭐가 답답하셨나요?

1번과 2번은 그럭저럭 괜찮았습니다. 그쵸? 왜냐하면 한번 봄으로써, 여러개의 인덱스들을 같이 제거할 수 있었습니다. 하지만 3, 4, 5번 단계에서는 한번 봤는데, 고작 1개의 후보만 지울수 있었습니다.

만약 3 번 단계에서, index 6과 같은 가장자리에 위치한 인덱스를 선택하지 않고, index 4나 5처럼 중간에 위치한 인덱스를 선택했다면, 잘하면 2개, 아니면 1개를 추가로 더 지울 수 있었을 텐데말입니다.

한 인덱스를 들쳐 봄으로써, 그 위치를 기준으로 오른쪽 전부, 혹은 왼쪽 전부를 추가로 지울 수 있습니다.

내가 선택한 인덱스를 기준으로, 왼쪽에 a개, 오른쪽에 b개가 존재한다면….. a개나 b개 둘중 하나가 추가로 지워집니다.

내가 선택한 인덱스를 기준으로, 왼쪽에 1개, 오른쪽에 b개가 존재한다고 할때…. 운이 좋으면 b개를 한번에 털어버릴 수 있지만, 그렇지 않을 경우에는 1개만 털수 있습니다.

가장 운이 좋지 않을때를 가정한다면…. 중간 부터 보는것이 가장 현명합니다. 중간을 선택한다면, 아무리 결과가 나빠도, 한번 볼때 절반정도는 추가적으로 없애버릴 수 있습니다.

3. 중간부터 탐색 (이분탐색)

찾아야 하는 후보군 중에서 가장 작은 index를 left, 가장 큰 index를 right라고 하겠습니다. 중간 index는 어떻게 구할까요? (left + right) / 2 를 계산함으로써 구해질 수 있습니다. 이것을 mid라고 부르겠습니다.

left = 4, right = 8 이라면 mid = (4 + 8) / 2 = 6 입니다. left = 3, right = 8 이라면 mid = (3 + 8) / 2 = 5 가 됩니다. (5와 6이 중간의 두개인데, 이중 왼쪽입니다.)

c. f. (left + right + 1) / 2 를 계산해서, 중간 두개중 오른쪽을 선택할 수도 있습니다. 하지만 여기에서는 중간 두개중 왼쪽을 선택하기로 합니다.

코드를 바로 보겠습니다.

int find(int x){
    /*
    	x를 담고 있는 위치를 반환한다. 만약 x가 배열안에 존재하지 않는다면, -1을 반환한다.
    	탐색할 배열은 전역으로 선언되어 있다.
    */
    int left = 0, right = n-1; // [left, right] 가 후보군.
    while(후보군이 있을때까지){
        int mid = (left + right) / 2;
        if(x < o[mid]){
            // 1....
        }else if(o[mid] < x){
            // 2...
        }else{
            return mid; // o[mid] == x 이므로!
        }
    }
    
    // 여기까지 도달했다는 것은, while안에서 return mid; 가 한번도 실행되지 않았다는 것이다.
    return -1; 
}

거의 다 왔습니다. 이제 코드의 빈칸을 채워봅시다.

1. x < o[mid] 인 경우: x < o[mid+1], x < o[mid+2], … 도 성립합니다. 그러니 [mid, right] 범위는 볼필요가 없습니다. mid를 기준으로 해서 오른쪽 후보군을 전부 제거해주면 되겠네요! right (후보군의 오른쪽 한계선) 을 mid - 1 로 변경해주면 됩니다.

2. o[mid] < x 인 경우: ….. o[mid-2] < x, o[mid-1] < x, 도 성립합니다. 그러니 [left, mid] 범위는 볼필요가 없습니다. mid를 기준으로 해서 왼쪽 후보군을 전부 제거해주면 되겠습니다. left (후보군의 왼쪽 한계선) 을 mid + 1로 변경해주면 됩니다.

int find(int x){
    /*
    	x를 담고 있는 위치를 반환한다. 만약 x가 배열안에 존재하지 않는다면, -1을 반환한다.
    	탐색할 배열은 전역으로 선언되어 있다.
    */
    int left = 0, right = n-1; // [left, right] 가 후보군.
    while(후보군이 있을때까지){ 
        int mid = (left + right) / 2;
        if(x < o[mid]){
            right = mid - 1;
        }else if(o[mid] < x){
            left = mid + 1;
        }else{
            return mid;
        }
    }
    
    // 여기까지 도달했다는 것은, while안에서 return mid; 가 한번도 실행되지 않았다는 것이다.
    return -1;
}

마지막입니다. 후보군이 없다는 것은 어떻게 알까요? left < right이면 아직 더 살펴봐야 할 것입니다. 그리고 left == right 이면 단 한개의 후보가 남았다는 뜻입니다. 그러니 left <= right 인 동안만 살펴보면 됩니다.

int find(int x){
    /*
    	x를 담고 있는 위치를 반환한다. 만약 x가 배열안에 존재하지 않는다면, -1을 반환한다.
    	탐색할 배열은 전역으로 선언되어 있다.
    */
    int left = 0, right = n-1; // [left, right] 가 후보군.
    while(left <= right){ 
        int mid = (left + right) / 2;
        if(x < o[mid]){
            right = mid - 1;
        }else if(o[mid] < x){
            left = mid + 1;
        }else{
            return mid;
        }
    }
    
    // 여기까지 도달했다는 것은, while안에서 return mid; 가 한번도 실행되지 않았다는 것이다.
    return -1;
}

c. f. 시간복잡도

이분탐색의 시간복잡도는 어떻게 될까요? 한번 값을 확인할때마다 확인해야할 것들이 절반씩 줄어들게 됩니다.

n개의 원소가 있다면…. 한번 확인후 n / 2개로.. 두번째 확인후 n / 2 / 2개로… 세번째는 n / 2 / 2 / 2… … k번째 확인후에는 $\frac{n}{2^{k}}$ 개로 줄어듭니다.

x번째를 확인하고 나서, 1개밖에 남지 않았다고 해보겠습니다. (저희는 이 x가 무엇인지 궁금합니다.)

\[\frac{n}{2^{x}} = 1\] \[n = 2^{x}\] \[x = log_{2}(n)\]

즉 원소의 갯수가 n개라면, 거기에 더불어 이 원소가 정렬되어 있다면, $log_{2}(n)$만에 원하는 값을 찾을 수 있습니다. (앞에서부터 탐색하는 경우는 O(n)입니다.)