Blog

C++ 이진 탐색(Binary Search) 구현 및 흔히 발생하는 오류

April 5, 2014

C++ 이진 탐색(Binary Search) 구현 및 흔히 발생하는 오류

이진 탐색

전 아직 Donald KnuthThe art of computer programming 을 본적은 없습니다만, 스택오버플로우에 올라온 질문 에 의하면, 이런 말을 했다고 합니다.

“Although the basic idea of binary search is comparatively straightforward, the details can be surprisingly tricky…”

무엇이 까다로운지는 아래서 다루겠습니다. 하지만 바이너리 서치가 고려해야될 점이 몇개 있다는건 알아두고 진행하지요.

1. Overview

이진 탐색 은 정렬된 자료를 대상으로 실행될 경우에만 유효합니다. 왜냐하면 방법 자체에서 이미 정렬되어 있다고 가정하기 때문입니다. 먼저 그림을 보시죠. 76을 찾고싶다고 할 때, 다음과 같이 이진 탐색이 진행됩니다.

결국 이진 탐색 이란 현재 자료의 좌측은 현재 값보다 작고, 우측은 현재값보다 크다고 가정하고 탐색하는 방법입니다. 따라서 최악의 경우 O(logn) 의 성능을 내며, 가장 빠를때는 O(1) 입니다. 당연히 일반적인 선형 탐색(Linear Search) 보다 빠르나 배열이 정렬되어 있어야 한다는 전제 조건이 붙습니다. 유사하게, Hash 의 경우에도 이진 탐색 보다 평균적으로 더 빠르지만 더 제약조건이 많죠.

2. Binary Search Implementation

이진 탐색 은 두 가지 버전으로 구현할 수 있습니다. 첫 째는 재귀(Reculsive) 고 두 번째는 반복(Interative) 입니다. 반복부터 보시겠습니다.

Iterative Version

int binary_search(int* arr, int length, int value) {

    if (arr == nullptr || length < 0)
        return -1;

    int left = 0;
    int right = length - 1;
    int mid;

    while(left <= right) {
        mid = left + (right - left) / 2;

        if(arr[mid] == value) {
            return mid;
        } else if (arr[mid < value]) {
            left = mid + 1;
        } else if (arr[mid] > value) {
            right = mid - 1;
        }
    }

    return -1;
}

Reculsive Version

int binary_search(int* arr, int value, int left, int right) {

    if(left > right) {
        return -1;
    }

    int mid = left + (right - left) / 2;

    if (arr[mid] == value)
        return mid;
    else if (arr[mid] > value) {
        binary_search_reculsive(arr, value, left, mid - 1);
    } else {
        binary_search_reculsive(arr, value, mid + 1, right);
    }

}

3. Problems

여기 에 의하면 Knuth는 TAOCP 에서 이진탐색은 1946년 에 발표되었으나, 그의 정확한 구현은 1962년 에 이루어졌다고 지적했습니다. 또한 Bentley는 벨 연구소나 IBM 에서 일하는 박사과정 학생들에게 두시간을 주고 이진검색을 구현하라고 했을때 90%가 버그 있는 코드를 제출했다고 말했습니다. 어떤 요소들이 이진 탐색의 구현을 어렵게 만드는 걸까요?

Numerical Underflows / Overflows

가장 흔히 발생하는 오류는 오버플로우입니다. 여기에 의하면, 프로그래머들은 종종 다음과 같이 문제가 있는 코드를 작성하곤 합니다.

1:     public static int binarySearch(int[] a, int key) {
2:         int low = 0;
3:         int high = a.length - 1;
4:
5:         while (low <= high) {
6:             int mid = (low + high) / 2;
7:             int midVal = a[mid];
8:
9:             if (midVal < key)
10:                 low = mid + 1
11:             else if (midVal > key)
12:                 high = mid - 1;
13:             else
14:                 return mid; // key found
15:         }
16:         return -(low + 1);  // key not found.
17:     }

6번째 줄을 주목해주세요. (low + high) / 2 는 중간값을 돌려주지만 그것은 int 의 범위 내에서 입니다. 무슨 말인고 하니, lowhigh 를 더했을 때 32bit int의 최대값인 (2^31 - 1) 보다 크다면, 오버플로우가 일어날겁니다. 그리고 음수값이 되겠지요. C라면 Unpredictable results를 만들거고 자바라면 ArrayindexOutofBoundException 이 발생할 겁니다. 따라서 6번째 줄의 코드는

 6:             int mid = low + ((high - low) / 2);

위와 같이 고치거나, >>> 연산자가 있는 언어라면

 6:             int mid = (low + high) >>> 1;

>>> 가 없는 CC++ 같은 언어라면 다음과 같이 고칠 수 있겠습니다.

 6:             mid = ((unsigned int)low + (unsigned int)high)) >> 1;

Handling of duplicate items

이진 탐색에서 단순히 값만 같은 원소를 돌려주는게 아니라, 첫 번째로 값이 같은(인덱스상에서 가장 좌측에 위치한) 원소를 돌려주려면 조금 생각을 해봐야합니다. 찾았을 경우 인덱스를 – 하면서 루프를 한번 더 돈다던가요.

Recursive vs Non-reculsive

어떤 구현이 현재의 자료의 사이즈와 형태탐색에서 더 나은 성능을 보여줄지 생각하고 결정해야합니다. 일반적으로는 재귀보다는 반복문이 스택으로 인한 오버헤드가 없어서 더 선호되는 편입니다.

Off-by-one errors

경계값 에러는 항상 발생합니다. 이를테면, 위 코드에서 5번째 줄을 다음과 같이 구현했을 경우

5:         while (low < high) {

원소가 { 0, 1 } 두개이고, 1을 찾고자 할때 찾지 못합니다. low == high 인 경우 루프를 돌지 않으니까요. 경계값을 올바르게 나누는 방법에 대해서 알고 싶으시다면 여기를 참조하시면 되겠습니다. 간단히 내용을 소개하자면, 중간 포지션을 기점으로 좌우를 나누는 로직을 다룬 내용인데 아래와 같습니다.

구분 left half right half
Natural Division 0 <= i < n/2 (n+1)/2 <= i < n
Left + division 0 <= i < (n+1) / 2 (n+1)/2 <= i < n
Right Division 0 <= i < n/2 n/2 <= i < n
Left cut out center division 0 <= i < (n+1)/2 – 1 (n+1)/2 <= i < n
Right cut out center division 0 <= i < n/2 n/2 + 1 <= i < n

사실 Natural Division 만 기억하고 계시면 될듯 합니다. 중간값을 포함하는 경우는 흔치 않고, 왼쪽에서 중간값을 커팅하냐 오른쪽에서 해내냐는 사실 별 의미가 없는것 같습니다. 다음 포스팅은 Binary Search Tree 구현과 DFS, BFS 가 될 것 같습니다. 감사합니다.

References

  1. http://flylib.com/books/en/2.300.1.75/1/
  2. http://mkseo.pe.kr/blog/?p=1502
  3. http://googleresearch.blogspot.kr/2006/06/extra-extra-read-all-about-it-nearly.html
  4. http://arxiv.org/ftp/arxiv/papers/1402/1402.4843.pdf
  5. http://stackoverflow.com/questions/504335/what-are-the-pitfalls-in-implementing-binary-search