[알고리즘 C언어] 4.2 이진 탐색 알고리즘

이번에는 이진 탐색 알고리즘을 알아봅시다.

이진 탐색 알고리즘은 특정 키순으로 정렬 상태의 배열에서 원하는 값의 요소를 빠르게 검색하는 알고리즘입니다. 순차적으로 비교하여 검색한다면 자료의 개수가 N개인 배열에서 최악의 경우 N번 비교해야 합니다. 하지만 이진 탐색 알고리즘으로 검색하면 logN 번이면 검색할 수 있습니다.

이진 탐색 알고리즘은 배열의 중간에 있는 요소와 비교해서 배열의 요소가 크면 재귀적으로 앞쪽 배열에서 검색하고 배열의 요소가 작으면 재귀적으로 뒤쪽 배열에서 검색합니다. 만약 같은 값이면 해당 인덱스를 반환합니다. 그리고 배열의 원소 개수가 0이면 재귀를 탈출하기 위해 인덱스 -1을 반환합니다.

이진 탐색 알고리즘(base:배열, asize:원소 개수, key:키, compare:  비교 알고리즘)

조건 (asize<0)    -1반환

gap := compare(base[asize/2],key)

조건 (gap is 0) asize/2 반환

조건(gap>0)    반환 이진 탐색 알고리즘(base, asize/2, key, compare);

조건(gap<0)    반환 이진 탐색 알고리즘(base+asize/2, asize-asize/2, key, compare);

이제 구체적으로 구현해 봅시다.

#include "common.h"
#include "Book.h"
typedef void *Key;
typedef void *Element;
typedef int (*Compare)(Element , Key);

이진 탐색 알고리즘은 정렬 상태의 배열과 검색 키, 비교 알고리즘을 요구합니다. 그리고 검색한 데이터가 있는 위치를 반환하기로 합시다.

Element *BinarySearch(Element *base,int asize,Key key, Compare compare)
{
    int gap = 0;

배열의 원소 개수가 0보다 작거나 같으면 검색 결과는 없습니다. 이 때는 0(NULL)을 반환합니다.

    if(asize<=0)
    {
        return 0;
    }

배열의 중간에 있는 요소와 키를 비교합니다.

    gap = compare(base[asize/2],key);

만약 차이가 없으면 중간에 있는 요소가 찾는 요소입니다.

    if(gap == 0)
    {
        return base+(asize/2);
    }

배열의 중간에 있는 요소가 크면 배열의 앞쪽에서 찾습니다. 이 때 재귀호출로 수행한 결과를 반환합니다.

    if(gap>0)
    {
        return BinarySearch(base,asize/2,key,compare);
    }

검색 키가 크면 배열의 뒤쪽에서 찾습니다. 이 때도 재귀호출로 수행한 결과를 반환합니다.

    return BinarySearch(base+(asize/2+1),asize - (asize/2+1),key,compare);
}
#define MAX_BOOK	10
Book *books[MAX_BOOK]={0};
void SimulationInit();
void Simulation();
void SimulationClear();
int main()
{
    SimulationInit();
    Simulation();
    SimulationClear();
    return 0;
}

void SimulationInit()
{

이진 탐색 알고리즘의 선행 조건은 입력 인자로 전달받은 배열은 정렬 상태여야 합니다. 이를 위해 도서 번호를 정렬 상태로 정의합시다.

    int bnum[MAX_BOOK] = {1,4,10,15,20,33,39,40,45,69};
    char title[MAX_TIT_LEN+1]="";
    char author[MAX_AUT_LEN+1]="";
    int i = 0;
    for(i=0; i<MAX_BOOK; ++i)
    {
        sprintf(title,"%010d",rand());
        sprintf(author,"%010d",rand());
        books[i] = New_Book(title,author,bnum[i]);
    }
}

void Simulation()
{
    Book **seat = 0;    
    int key = 0;
    printf("검색할 도서 번호:");
    scanf_s("%d",&key);

이진 탐색 알고리즘으로 검색한 후에 검색 결과를 출력합시다.

    seat = (Book **)BinarySearch(books,MAX_BOOK,(Key)key,(Compare)Book_CompareNum);
    if(seat == 0)
    {
        printf("%d 번 도서 없음\n",key);
    }
    else
    {
        printf("검색 결과:");
        Book_View(*seat);
    }
}

void SimulationClear()
{
    int i = 0;
    for(i=0; i<MAX_BOOK; ++i)
    {
        Delete_Book(books[i]);
    }
}