6.3 이진 탐색(Binary Search) [디딤돌 자료구조와 알고리즘 with C++]

6.3 이진 탐색(Binary Search)

이진 탐색(Binary Search) 알고리즘은 정렬 상태의 배열에서 원하는 자료를 탐색하는 알고리즘으로 재귀적인 방법으로 구현할 수 있는 대표적인 알고리즘입니다.

 

배열의 중간에 있는 요소와 검색 자료를 비교하여 크면 뒤쪽 배열에서 재귀적으로 탐색하고 작으면 앞쪽 배열에서 재귀적으로 탐색합니다. 만약 같은 자료를 찾거나 배열의 원소 개수가 0이면 탐색을 끝냅니다.

위치 BinarySearch(base: 배열, n: 원소 개수, value: 검색할 값)

    조건 n<=0

        0 반환

    gap = base[n/2] - value;

    if(gap == 0)

        반환 base + n/2

    if(gap>0)

        반환 BinarySearch(base,n/2, fun)

    반환 BinarySearch(base+n/2+1,n - n/2, fun)

 

순차 탐색한다면 최악의 경우 모든 요소와 비교해야 하므로 O(n) 성능을 보입니다. 하지만 이진 탐색에서는 n/(2의 0승), n/(2의 1승), n/(2의 2승),...,n/(2의 h승)개일 때 가운데 요소와 1번씩만 수행합니다. n/(2의 h승)이 1이면 더이상 비교하지 않으므로 O(logn) 성능을 보입니다.

 

 

6.3.1 순차 탐색과 이진 탐색의 성능 비교

순차 탐색 알고리즘과 이진 탐색 알고리즘을 구현한 후에 둘의 성능 차이를 확인해 봅시다.

#include <iostream>

#include <string>

#include <time.h>

#include <stdlib.h>

using namespace std;

먼저 순차 탐색을 구현합시다.

int *sequentailsearch(int *base, size_t n, int value)

{

순차적으로 배열의 각 요소와 검색할 자료를 비교하세요.

    for(size_t s = 0; s<n; s++)

    {

        if(base[s] == value)

        {

같은 값을 발견하면 해당 위치를 반환합니다.

            return base+s;

        }

    }

모든 요소와 비교해도 같은 자료가 없으면 0을 반환하세요.

    return 0;

}

이번에는 이진 탐색을 구현합시다.

int *binarysearch(int *base, size_t n, int value)

{

배열의 크기가 0보다 작거나 같으면 재귀 함수를 탈출합니다.

    if(n<=0)

    {

        return 0;

    }

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

    int gap = base[n/2] - value;

    if(gap == 0)

    {

차이가 없으면 배열의 중간에 있는 요소가 있는 위치를 반환하세요.

        return base + n/2;

    }

    if(gap>0)

    {

검색할 자료가 작으면 gap은 0보다 큽니다. 이때는 배열의 앞쪽에서 검색합니다.

        return binarysearch(base,n/2,value);

    }

그렇지 않으면 배열의 뒤쪽에서 검색합니다.

    return binarysearch(base+n/2+1, n-n/2-1,value);

}

 

int main()

{

충분히 큰 배열을 선언하세요.

    int arr[100000];

    srand((unsigned)time(0));//랜덤 시드 값 설정

 

이진 탐색은 선행 조건이 정렬 상태여야 한다는 것이죠. 다음처럼 정렬 상태로 배열의 요소를 설정하세요.

    for(int i = 0; i<100000;i++)

    {

        arr[i] = i*5+rand()%5;

    }

 

테스트는 100 개의 요소 중에서 탐색하는 것과 10만 개의 요소 중에서 탐색하는 것을 비교할게요. 탐색에 걸리는 시간이 짧아 테스트를 만 번 하는데 걸리는 시간으로 비교해 보기로 해요.

 

먼저 순차 탐색으로 100 개의 요소 중에 탐색하는 것을 만 번 수행하세요.

    clock_t st,et;

    st = clock();

    for(int tc = 0; tc<10000; tc++)

    {

        int index = rand()%100;       

        sequentailsearch(arr,100,arr[index]);

    }

    et = clock();

수행에 걸린 시간을 출력하세요.

    cout<<"100 개에서 순차 탐색으로 10000번 수행에 걸린 시간:"<<et-st<<endl;

 

순차 탐색으로 10만 개 요소 중에 탐색하는 것을 만 번 수행하세요.

    st = clock();

    for(int tc = 0; tc<10000; tc++)

    {

        int index = rand()%100000;       

        sequentailsearch(arr,100000,arr[index]);

    }

    et = clock();

수행에 걸린 시간을 출력하세요.

    cout<<"10만 개 순차 탐색으로 10000번 수행에 걸린 시간:"<<et-st<<endl;

 

 

 

이진 탐색으로 100개의 요소 중에 탐색하는 것을 만 번 수행하세요.

    st = clock();

    for(int tc = 0; tc<10000; tc++)

    {

        int index = rand()%100;       

        binarysearch(arr,100,arr[index]);

    }

    et = clock();

수행에 걸린 시간을 출력하세요.

    cout<<"100 개에서 이진 탐색으로 10000번 수행에 걸린 시간:"<<et-st<<endl;

 

이진 탐색으로 10만 개의 요소 중에 탐색하는 것을 만 번 수행하세요.

    st = clock();

    for(int tc = 0; tc<10000; tc++)

    {

        int index = rand()%100000;       

        binarysearch(arr,100000,arr[index]);

    }

    et = clock();

수행에 걸린 시간을 출력하세요.

    cout<<"10만 개에서 이진 탐색으로 10000번 수행에 걸린 시간:"<<et-st<<endl;

   

    return 0;

}

 

▷ 실행 결과

100 개에서 순차 탐색으로 10000번 수행에 걸린 시간:3

10만 개 순차 탐색으로 10000번 수행에 걸린 시간:782

100 개에서 이진 탐색으로 10000번 수행에 걸린 시간:4

10만 개에서 이진 탐색으로 10000번 수행에 걸린 시간:10

 

실험에서 순차 탐색은 자료의 수를 1000배 늘렸을 때 250배 정도 걸렸는데 이진 탐색은 2.5배 정도 걸렸습니다. 이처럼 이진 탐색은 자료의 개수가 많이 늘어나도 실제 수행 속도는 크게 늘지 않음을 알 수 있습니다. 수행 속도가 O(logn)이기 때문입니다.