C++로 구현하는 이진 탐색 알고리즘: 배열에서 특정 검색 시퀀스 찾기

이 글에서는 정렬된 배열 안에서 특정 검색 시퀀스(연속된 숫자 나열)의 존재 여부를 확인하는 이진 탐색(Binary Search) 알고리즘을 C++로 구현하는 방법을 소개합니다. 이진 탐색은 탐색 범위를 절반씩 줄여가며 값을 찾는 대표적인 탐색 기법으로, 시간 복잡도는 O(log n)으로 매우 효율적입니다. 단, 이진 탐색이 올바르게 동작하려면 배열이 반드시 오름차순으로 정렬되어 있어야 한다는 점에 유의해야 합니다.

필요한 단계와 의사 코드(Pseudocode)

프로그램의 전체적인 동작 흐름은 다음과 같습니다.

Begin
    BinarySearch() 함수는 데이터 배열 'arr', 값의 개수 'n', 시작 인덱스와 끝 인덱스,
    반복 횟수(iteration count), 그리고 검색할 첫 번째 요소 b[0]를 인자로 받습니다.
    반복 카운터를 증가시키고, 검색할 항목 값을 a[mid]와 비교합니다.
    item < a[mid]이면 전반부를, 그렇지 않으면 후반부를 선택하여 탐색을 계속 진행합니다.
    찾은 인덱스 값을 main()으로 반환합니다.
    main()에서는 검색 시퀀스의 나머지 항목들을 배열의 연속된 항목들과 순차적으로 비교합니다.
    시퀀스가 발견된 인덱스 범위를 출력합니다.
End.

예제 코드

#include<iostream>
using namespace std;
int BinarySearch(int a[], int start, int end, int item, int iter) {
    int i, mid;
    iter++;
    mid = start+ (end-start+1)/2;
    if(item > a[end] || item < a[start] || mid == end) {
        cout<<"\nNot found";
        return -1;
    } else if(item == a[mid]) {
        return mid;
    } else if(item == a[start]) {
        return start;
    } else if(item == a[end]) {
        return end;
    } else if(item > a[mid])
        BinarySearch(a, mid, end, item, iter);
        else
            BinarySearch(a, start, mid, item, iter);
    }
int main() {
    int n, i, flag=0, Bin, len = 9, a[10]={1, 7, 15, 26, 29, 35, 38, 40, 49, 51};
    cout<<"\nEnter the number of element in the search sequence: ";
    cin>>n;
    int b[n];
    for(i = 0; i < n; i++) {
        cin>>b[i];
    }
    Bin = BinarySearch(a, 0, len, b[0], 0);
    if (Bin == -1) {
        cout<<"\nNot found.";
        return 0;
    } else {
        for(i = Bin; i < n+Bin; i++)
            if(a[i] != b[i-Bin])
                flag = 4;
                if(flag == 4)
                    cout<<"\nNot found.";
                else
                    cout<<"\nSequence found between index "<<Bin<<" and "<<Bin+n<<".";
    }
    return 0;
}

코드 설명

BinarySearch() 함수는 재귀적으로 호출되며, 매번 탐색 범위를 절반으로 줄여나갑니다. 중간 인덱스는 mid = start + (end-start+1)/2 공식으로 계산됩니다. 검색하려는 값이 현재 범위의 최대값보다 크거나 최소값보다 작으면 더 이상 탐색할 필요가 없으므로 "Not found" 메시지를 출력하고 -1을 반환합니다. 값이 중간 요소, 시작 요소, 또는 끝 요소와 일치하면 해당 인덱스를 즉시 반환합니다.

main() 함수에서는 먼저 사용자로부터 검색 시퀀스의 길이와 요소들을 입력받습니다. 그런 다음 시퀀스의 첫 번째 요소(b[0])를 이진 탐색으로 찾아 그 위치(Bin)를 얻습니다. 이후 배열의 해당 위치부터 시퀀스 길이만큼의 구간이 입력된 시퀀스와 연속적으로 일치하는지 확인하고, 일치하면 시작 인덱스와 끝 인덱스를 출력합니다.

실행 결과

Enter the number of element in the search sequence: 4
15
26
29
35
Sequence found between index 2 and 6.

위 실행 결과에서 사용자는 길이가 4인 시퀀스 {15, 26, 29, 35}를 입력했습니다. 프로그램은 첫 번째 요소인 15를 이진 탐색으로 찾아낸 뒤, 배열에서 연속된 네 개의 값이 모두 일치하는지 검사하여 해당 시퀀스가 인덱스 2부터 6 사이에 존재함을 출력합니다.