Algorithm/Theory

탐색 알고리즘 - 이진 탐색(Binary Search)

hyunipad 2021. 1. 14. 22:31
반응형

이진 탐색(Binary Search)은 정렬된 데이터 집합에서 사용할 수 있는 고속 탐색 알고리즘입니다.

 

이진 탐색을 수행하는 과정은 아래와 같습니다.

 

  1. 데이터 집합의 중앙에 있는 데이터를 고른다.
  2. 중앙에 있는 데이터값과 찾고자 하는 목표 값을 비교한다.
  3. 목표 값이 중앙에 있는 요소보다 작다면 중앙을 기준으로 왼쪽 데이터에 대해 새로 검색을 실시하고 크다면 오른쪽 데이터에 대해 새로이 검색을 실시합니다.
  4. 찾고자 하는 목표 값을 찾을 때까지 1~3번의 과정을 반복합니다.

 

예를 들어보자면, 아래와 같이 정렬된 데이터 집합이 있습니다. 이 데이터 집합에서 50을 찾아 보겠습니다.

 

1  5  18  20  35  40  46  50  70  90

 

먼저 중앙에 있는 요소를 고릅니다. 주어진 데이터 집합의 사이즈를 구하여 반으로 나눈 것이 중앙의 인덱스 번호가 됩니다. 이 배열에서 중앙의 데이터 값은 40 입니다. 

 

1  5  18  20  35  40  46  50  70  90

 

우리가 찾고자 하는 목표 값 50이 중앙의 데이터보다 크기 때문에 오른쪽 데이터에 대해 새로 검색을 실시 합니다.

 

46  50  70  90

 

중앙에 위치한 데이터 값 70보다 목표 값이 작기 때문에 왼쪽 데이터에 대해 새로 검색을 실시하고, 다음 중앙의 요소인 50이 목표 값 50과 일치하기 때문에 탐색은 끝이 나게됩니다.

 

 46  50

 

이진 탐색의 성능 측정

이진 탐색은 탐색을 실시할 때마다 탐색 대상의 범위가 반으로 줄어듭니다.

즉 처음 탐색을 시도하면 원본 데이터 범위의 1/2 

그다음 시도했을 때는 원본 데이터의 반의 반 1/4 그다음은 1/16 ....

이런 식으로 범위가 계속 줄어들어 마침내 '1'이 되면 데이터를 찾아내고 탐색을 종료합니다.

 

이 규칙을 수식으로 나타내면 ( n = 데이터 집합의 크기, x = 반복 횟수) 

1 = n * (1/2)x 

1 = n * 1/2x

2x = n

이까지 오셨다면, 양변의 로그를 취해주시면

x = log2n 라는 식을 구할 수 있습니다.

 

이식이 의미하는 것은 크기가 100만개인 데이터 집합을 탐색한다고 했을 때 탐색 횟수는 20회 1000만개인 데이터 집합에선 23회 탐색을 반복하면 목표 값을 찾아낼 수 있다는 것을 의미합니다.

왜 이진 탐색이 고속 탐색이라고 불리는 지 알 수 있는 대목이네요.

 

이진 탐색의 구현

아래는 이진 탐색 코드 예시입니다.

#include <stdio.h>
#include <stdlib.h>
 
int BinarySearch(int DataSet[], int Size, int Target) {
    int Left; // 왼쪽 인덱스
    int Right; // 오른쪽 인덱스
    int Mid; // 중간 인덱스
 
    Left = 0; // 처음 인덱스
    Right = Size - 1; // 끝 인덱스
 
    while (Left <= Right) { // 탐색 인덱스의 범위가 0이 될때까지 루프를 반복한다.
        Mid = (Left + Right) / 2; // 중간 인덱스 번호 찾기
 
        if (Target == DataSet[Mid]) { // 타겟 일치하면
            return Mid; // 리턴
        }
        else if (Target > DataSet[Mid]) { // 타겟이 저 크다면
            Left = Mid + 1; // 왼쪽 인덱스를 옮긴다
        }
        else { // 타겟이 작은쪽에 있다면
            Right = Mid - 1; // 오른쪽 인덱스를 옮긴다
        }
    }
    return 0;
}
 
int CompareInt(const void* elem1, const void* elem2){
 
    if (*(int*)elem1 > * (int*)elem2) {
        return 1;
    }
    else if ( *(int*)elem1 < *(int*)elem2) {
        return -1;
    }
    else {
        return 0;
    }
}
 
int main(void) {
    int Dataset[] = { 1, 9 ,4 ,6, 40, 35, 90, 30, 60, 20 };
    int i = 0;
    int Found = 0;
    int Length = sizeof Dataset / sizeof Dataset[0];
 
    qsort((void*)Dataset, Length, sizeof Dataset[0], CompareInt);
    Found = BinarySearch(Dataset, Length, 6);
 
    printf("찾아낸 목표 값의 인덱스 번호 : %d " ,Found);
 
    return 0;
}

 

현재 위의 예시 코드는 int형을 예시로 했지만, 적절한 수정을 통해 여러 가지의 데이터 집합들을 비교할 수 있습니다.

또한 C언어에서는 퀵정렬과 마찬가지로 이진 탐색을 함수로써 제공해 주고 있습니다.

void* bsearch(
    const void* key, // 찾고자 하는 목표 값의 주소
    const void* base, // 데이터 집합 배열의 주소
    size_t num, // 데이터 집합의 갯수
    size_t width, // 데이터 요소의 크기
    int (__cdec1 *compare) (const void*, const void*) // 비교 함수에 대한 포인터
);

 

아래는 이진 탐색 함수인 bsearch()의 예시 코드입니다.

#include <stdio.h>
#include <stdlib.h>
 
int CompareInt(const void* elem1, const void* elem2){
 
    if (*(int*)elem1 > * (int*)elem2) {
        return 1;
    }
    else if ( *(int*)elem1 < *(int*)elem2) {
        return -1;
    }
    else {
        return 0;
    }
}
 
int main(void) {
    int Dataset[] = { 1, 9 ,4 ,6, 40, 35, 90, 30, 60, 20 };
    int Length = sizeof Dataset / sizeof Dataset[0];
    int Target = 4;
    int* Found = 0;
 
    qsort((void*)Dataset, Length, sizeof Dataset[0], CompareInt);
 
    Found = bsearch((void*)&Target,(void*)Dataset, Length, sizeof Dataset[0], CompareInt);
 
    printf("찾아낸 목표 값의 인덱스 번호 : %d " ,Found-Dataset); // Found-DataSet => Found 의 인덱스 번호
 
    return 0;
}

이진 탐색은 빠른 탐색 알고리즘이지만, 단점이 있습니다.

바로 정해진 크기의 데이터 집합만 탐색할 수 있다는 것입니다.

가령 링크드 리스트같이 처음과 끝이 있지만, 그 중앙 요소를 알 수 없는 데이터의 경우는 탐색이 불가합니다.

 

그러한 단점을 해결 해주는 자료구조가 바로 '이진 탐색 트리' 입니다.

 

 

반응형
저작자표시