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)이기 때문입니다.