C언어 | 이진검색(Binary Search) | 자료구조

이진검색은 데이터가 키 값으로 정렬이 되있어야 제대로된 검색이 가능하다.

 

예를 들어 아래와 같은 오름차순 정렬한 배열이 있다.

 

[1, 3, 5, 7, 9, 11, 13, 15, 17, 19]

 0   1  2  3  4    5    6    7    8    9

 

아래의 숫자는 배열의 인덱스다.

 

여기서 15를 검색한다. 이진 검색은 양끝이 필요하다. 인덱스 0과 9 를 더해서 2로 나눈다. 나머지를 버리면 4가 나온다. 이것이 배열의 중앙에 있는 값이다. array[인덱스 중앙] 인 array[4] = 9 를 얻는다.

 

array[4] = 9 와 키값인 15를 비교한다. 키값이 더 크다. 오름 차순 정렬이니까 찾는 값은 9보다 오른쪽에 있어야 한다. 현재 9는 인덱스의 중앙에 있다. 왼쪽의 범위였던 0을 중앙인덱스 + 1인 5로 위치시킨다. 오른쪽 끝은 9였으니까 다시 (9 + 5) / 2 를 한다. 인덱스 7이다. arr[7] 과 키값 15는 일치하므로 현재의 인덱스인 m을 리턴한다.

 

이 내용이 아래 함수이다. 이진 검색은 선형 검색처럼 모든 요소를 확인할 필요가 없기 때문에 시간이 단축된다. 대신 미리 정렬해두지 않으면 제대로된 값을 얻을 수 없다. 데이터를 빈번히 업데이트 하는 자료에는 적합하지 않고 데이터는 변동이 적은데 검색량이 많은 곳에 사용할 수 있다.

int binarySearch(const int arr[], int pLeft, int pRight, int key)
{

    pRight -= 1;

    while (pLeft <= pRight){

        int median =  (pLeft + pRight) / 2;

        if (arr[median] == key){
            return median;
        }
        if (arr[median] < key){);
            pLeft = median + 1;
        }
        else {
            pRight = median - 1;
        }
    }
    return -1;
}

 

* 이진 검색을 위해서는 먼저 정렬을 해둬야 한다.

 

버블 정렬에 대하여는 이전 포스트를 참고한다.

C언어 | 버블정렬(Bubble Sort) 과 선형검색 (Linear Search) | 동적 메모리 할당

 

결과를 콘솔에 출력하면서 숫자를 따라가면 한결 수월하다. 자료 구조의 설명은 그림으로 많이 표현하거나 이렇게 숫자를 출력해보는게 도움이 된다.

 

 

*전체 소스코드

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

#define LINE           printf("---------------------------------------------\n")
#define DOUBLE_LINE    printf("\n=============================================\n\n")

void bubbleSort(int a[], int size);
void fillArrayRandom(int arr[], int count, int range);
void showArray(int arr[], int count);
int binarySearch(const int arr[], int pleft, int pright, int key);

int main(int argc, char const *argv[])
{
    DOUBLE_LINE;
    srand(time(NULL));

    /* 이진 검색 binary search */
    int count = 15; // 배열의 개수
    int *array = calloc(count, sizeof(int)); // count * 4 바이트 배열 동적할당
    int key = 15; // 검색할 값

    printf("[배열생성 및 정렬 요소 [%d]개 - 이진 검색]\n", count);
    LINE;
    fillArrayRandom(array, count, 20); // 난수를 배열에 채운다
    showArray(array, count);
    
    // 이진 검색 전에 소트한다.
    bubbleSort(array, count);
    showArray(array, count);

    // 이진 검색
    result = binarySearch(array, 0, count, key);

    (result == -1) ? printf("찾는 요소 %d가 배열에 없습니다...\n", key) : 
                     printf("요소를 찾았습니다. 인덱스 (%d) 값 = %d\n", result, key);
    free(array);
    DOUBLE_LINE;

    array = calloc(count, sizeof(int)); // count * 4 바이트 배열 동적할당
    key = 8; // 검색할 값

    for (int i = 0; i < count; i++)
    {
        array[i] = 2 * i;
    }
    showArray(array, count);

    result = binarySearch(array, 0, count, key);

    (result == -1) ? printf("찾는 요소 %d가 배열에 없습니다...\n", key) : 
                     printf("요소를 찾았습니다. 인덱스 (%d) 값 = %d\n", result, key);

    free(array);

    return 0;
}

int binarySearch(const int arr[], int pLeft, int pRight, int key)
{

    pRight -= 1;

    while (pLeft <= pRight){

        int median =  (pLeft + pRight) / 2;

        if (arr[median] == key){
            printf("MATCH!! at pleft[%d], pright[%d]\n", pLeft, pRight);
            return median;
        }
        if (arr[median] < key){
            printf("R:: left : %d, right :%d, arr[%d] = %d\n",pLeft , pRight, median, arr[median]);
            pLeft = median + 1;
        }
        else {
            printf("L:: left : %d, right :%d, arr[%d] = %d\n",pLeft , pRight, median, arr[median]);
            pRight = median - 1;
        }
    }
    return -1;
}

void bubbleSort(int arr[], int size)
{

    int i, j;

    for (i = 0; i < size-1; i++)
    {
        for (int j = size-1; j > i; j--)
        {
            if(arr[j-1] > arr[j])
                swap(int, arr[j-1], arr[j]);
        }
    }
}

void showArray(int arr[], int count)
{   
    printf("[");
    for (int i = 0; i < count; i++)
    {
        printf("%d, ",arr[i]);
    }
    printf("]\n");
}

void fillArrayRandom(int arr[], int count, int range)
{
    for (int i = 0; i < count; i++)
    {
        arr[i] = rand() % range + 1;
    }
}