Algorithm Training – 이진 탐색

요즘들어 다시 알고리즘 이론 공부를 시작하고 있다. 이글에서는 이진 탐색 알고리즘 (Binary Search Algorithm)을 공부한 내용을 간단하게 정리한다. 선형탐색과 달리 검색 범위를 매회 절반정도로 감축함으로서 효율을 높이는 탐색 방법이다. 탐색 범위의 중간에 위치한 요소를 가져와, 찾고자 하는 키워드와 비교해서 범위를 점점 줄여나간다. 하지만 그 때문에 요소가 오름차순 또는 내림차순으로 정렬된 배열에서만 작동한다.

본 알고리즘의 기본 구현 코드는 다음과 같다. 10개의 숫자 원소들 중에서 6을 찾는 소스코드. 이때 배열의 숫자 원소들은 오름차순으로 배열되어 있다.

#include <iostream>

int search(const int array[], int n, int keyword) {
    int left = 0;
    int right = n;
    do {
        int center = (left + right) / 2;
        if (keyword == array[center]) {
            return center;
        } else if (keyword < array[center]) {
            right = center - 1;
        } else {
            left = center + 1;
        }
    } while (left <= right);
}

int main(void) {
    int array[] = {1, 2, 4, 5, 6, 7, 11, 13, 15, 19};
    int n = sizeof(array) / sizeof(int);
    int keyword = 6;

    int result = search(array, n, keyword);
    std::cout << result;
}

다음 코드가 수행하는 작업을 그림으로 그려보면 다음과 같다. 때에 따라서는 선형 탐색이 더 빠를 수도 있겠지만, 자료양이 더 많을수록 이진탐색을 이용하는것이 조금 더 유리한것으로 보인다.

직접 그려본 탐색 과정

오름차순 배열을 기준으로, 가운데에 위치한 값이 찾는 값보다 작을 경우 오른쪽 탐색 범위를 줄이고, 반대의 경우(가운데에 위치한 값이 찾는 값보다 클 경우)에는 왼쪽의 탐색 범위를 절반씩 줄인다.

stdlib.h에서 제공하는 bsearch 함수를 이용해서 이진탐색 할 수도 있다. bsearch 함수를 사용한 코드는 아래와 같다.

#include <stdio.h>
#include <stdlib.h>

int int_cmpr(const int *a, const int *b) {
    if (*a > *b)
        return 1;
    else if (*a < *b)
        return -1;
    else return 0;
}

int main(void) {
    int array[] = {1, 2, 4, 5, 6, 7, 11, 13, 15, 19};
    int n = sizeof(array) / sizeof(int);
    int keyword = 6;

    int* p = (int *)(bsearch(&keyword, array, n, sizeof(int), (int (*)(const void *, const void *)) int_cmpr));

    if (p == NULL)
        puts("search failed");
    else
        printf("%d is in x[%d]\n", keyword, (int) (p - array));
    free(array);
    return 0;
}

각 값을 비교 하는 함수를 함수 포인터로 넘기는 것을 볼 수 있다. int_cmpr 함수는 오름차순 상태의 배열에서 탐색을 수행할 때 사용되도록 작성된 것이고, 리턴 값을 1을 -1로 -1을 1로 바꿔준다면 내림차순 배열에서 작동할 수 있다.

이진 탐색의 시간 복잡도는 곧 N을 절반으로 몇번 나눈 뒤에 하나의 결과값을 얻을 수 있냐는 것이므로

다음과 같이 계산할 수 있었다.

Leave a Reply

Your email address will not be published. Required fields are marked *