C++로 비교하는 이진 탐색 vs 순차 탐색: 어느 쪽이 더 빠를까?

이진 탐색(Binary Search)과 순차 탐색(Sequential Search, 선형 탐색)은 컴퓨터 프로그래밍에서 배열 안의 특정 요소를 찾을 때 널리 사용되는 대표적인 탐색 알고리즘입니다. 이진 탐색의 시간 복잡도는 O(log n), 순차 탐색의 시간 복잡도는 O(n)입니다.

이진 탐색은 탐색 범위를 절반씩 줄여 나가기 때문에 데이터가 많을수록 압도적으로 빠르지만, 배열이 반드시 정렬되어 있어야 한다는 전제 조건이 필요합니다. 반면 순차 탐색은 처음부터 끝까지 하나씩 비교하므로 상대적으로 느리지만, 정렬되지 않은 데이터에서도 동작한다는 장점이 있습니다.

알고리즘

이진 탐색(Binary Search)

시작
    이진 탐색 알고리즘:
    데이터 배열 'arr', 값의 개수 'n', 시작·끝 인덱스,
    반복 횟수, 찾으려는 요소(item)를 인자로 받는 BinarySearch() 함수를 정의한다.
    반복 카운터를 증가시키고 찾는 값과 a[mid](중간값)를 비교한다.
    item < a[mid]이면 전반부를, 그렇지 않으면 후반부를 선택하여 탐색을 계속한다.
    탐색에 성공하면 반복 횟수를 반환한다.
끝

예제 코드

아래 코드는 크기 10의 정렬된 배열에서 같은 값을 이진 탐색과 순차 탐색으로 각각 찾아 보고, 어느 쪽이 더 적은 반복으로 탐색에 성공했는지 비교하는 프로그램입니다.

#include<iostream>
using namespace std;

int BinarySearch(int a[], int start, int end, int item, int iter) {
    int i, mid;
    cout<<"\n반복 "<<iter+1;
    iter++;
    mid = start + (end-start+1)/2;
    if(item > a[end] || item < a[start] || mid == end) {
        cout<<"\n찾지 못했습니다";
        return iter;
    } else if(item == a[mid]) {
        cout<<"\n항목을 "<<mid<<" 인덱스에서 찾았습니다.";
        return iter;
    } else if(item == a[start]) {
        cout<<"\n항목을 "<<start<<" 인덱스에서 찾았습니다.";
        return iter;
    } else if(item == a[end]) {
        cout<<"\n항목을 "<<end<<" 인덱스에서 찾았습니다.";
        return iter;
    } else if(item > a[mid])
        BinarySearch(a, mid, 9, item, iter);
    else
        BinarySearch(a, start, mid, item, iter);
}

int LinearSearch(int a[], int n, int item) {
    int i;
    for(i = 0; i < n; i++) {
        cout<<"\n반복 "<<i+1;
        if(a[i] == item) {
            cout<<"\n항목을 "<<i<<" 인덱스에서 찾았습니다.";
            return i+1;
        }
    }
    cout<<"\n찾지 못했습니다";
}

int main() {
    int n, i, B, L, a[10]={2, 7, 14, 24, 26, 35, 38, 41, 49, 53};
    cout<<"\n찾을 요소를 입력하세요: ";
    cin>>n;
    cout<<"\n\n\t\t\t이진 탐색 :";
    B = BinarySearch(a, 0, 9, n, 0);
    cout<<"\n\n\t\t\t순차 탐색 :";
    L = LinearSearch(a, 10, n);
    if(L > B)
        cout<<"\n\n이 탐색에는 이진 탐색이 더 효율적입니다.";
    else if(L < B)
        cout<<"\n\n이 탐색에는 순차 탐색이 더 효율적입니다.";
    else
        cout<<"\n\n두 방식 모두 이 탐색에서 동일하게 효율적입니다.";
    return 0;
}

실행 결과

찾을 요소를 입력하세요: 7
이진 탐색 :
반복 1
반복 2
반복 3
반복 4
항목을 1 인덱스에서 찾았습니다.
순차 탐색 :
반복 1
반복 2
항목을 1 인덱스에서 찾았습니다.
이 탐색에는 순차 탐색이 더 효율적입니다.

찾을 요소를 입력하세요: 53
이진 탐색 :
반복 1
항목을 9 인덱스에서 찾았습니다.
순차 탐색 :
반복 1
반복 2
반복 3
반복 4
반복 5
반복 6
반복 7
반복 8
반복 9
반복 10
항목을 9 인덱스에서 찾았습니다.
이 탐색에는 이진 탐색이 더 효율적입니다.

찾을 요소를 입력하세요: 1
이진 탐색 :
반복 1
찾지 못했습니다
순차 탐색 :
반복 1
반복 2
반복 3
반복 4
반복 5
반복 6
반복 7
반복 8
반복 9
반복 10
찾지 못했습니다
이 탐색에는 이진 탐색이 더 효율적입니다.

결과 분석

① 7을 찾는 경우: 찾는 값이 배열 앞쪽(인덱스 1)에 있어서, 처음부터 순서대로 확인하는 순차 탐색이 단 2번의 반복으로 찾아냈습니다. 반면 이진 탐색은 중간값과 비교하며 범위를 좁혀 가는 과정 때문에 4번의 반복이 필요했습니다.

② 53을 찾는 경우: 값이 배열 맨 뒤(인덱스 9)에 있어서 순차 탐색은 10개 요소를 모두 확인해야 했습니다. 이진 탐색은 첫 번째 비교만으로 해당 위치를 찾아냈습니다.

③ 1을 찾는 경우(탐색 실패): 배열에 존재하지 않는 값입니다. 이진 탐색은 첫 번째 비교만으로 값이 탐색 범위 밖에 있음을 판단하고 종료한 반면, 순차 탐색은 '없다'는 사실을 확인하기 위해 10개 요소를 모두 살펴야 했습니다.

결론적으로, 찾는 값이 배열 앞쪽에 있거나 데이터 양이 아주 적다면 순차 탐색이 더 적은 반복으로 끝나는 경우도 있습니다. 하지만 일반적으로 데이터가 많고 정렬되어 있다면 이진 탐색이 훨씬 효율적입니다. 최악의 경우 순차 탐색은 O(n), 이진 탐색은 O(log n)이므로, 데이터 크기가 커질수록 두 방식의 성능 차이는 급격히 벌어집니다.