삼항 검색(Ternary Search) 알고리즘: 개념부터 C++ 구현까지

삼항 검색(Ternary Search)은 이진 탐색(Binary Search)과 마찬가지로 정렬된 리스트를 하위 리스트로 나누어 탐색하는 알고리즘입니다. 이진 탐색이 리스트를 두 부분으로 나누는 것과 달리, 삼항 검색은 두 개의 중간값(mid)을 사용하여 리스트를 세 부분으로 분할합니다. 리스트를 더 많은 구간으로 나눌수록 키 값을 찾기 위해 확인해야 할 범위가 빠르게 줄어들어 탐색 효율이 향상됩니다.

삼항 검색의 복잡도

시간 복잡도(Time Complexity): O(log₃ n)
공간 복잡도(Space Complexity): O(1)

입력 및 출력 예시

입력:
정렬된 데이터 목록: 12 25 48 52 67 79 88 93
탐색할 키 값: 52
출력:
Item found at location: 3

알고리즘

삼항 검색의 기본 동작 절차는 다음과 같습니다.

ternarySearch(array, start, end, key)

입력 − 정렬된 배열, 시작 위치와 끝 위치, 그리고 찾으려는 키 값

출력 − 키 값이 존재하면 해당 위치(index), 존재하지 않으면 유효하지 않은 위치(-1)

Begin
    if start <= end then
        midFirst := start + (end - start) / 3
        midSecond := midFirst + (end - start) / 3
        if array[midFirst] = key then
            return midFirst
        if array[midSecond] = key then
            return midSecond
        if key < array[midFirst] then
            call ternarySearch(array, start, midFirst-1, key)
        if key > array[midSecond] then
            call ternarySearch(array, midSecond+1, end, key)
        else
            call ternarySearch(array, midFirst+1, midSecond-1, key)
    else
        return invalid location
End

C++ 구현 예제

다음은 삼항 검색을 재귀 방식으로 구현한 C++ 코드입니다.

#include<iostream>
using namespace std;

int ternarySearch(int array[], int start, int end, int key) {
    if(start <= end) {
        int midFirst = (start + (end - start) / 3);   // 첫 번째 구간의 중간 지점
        int midSecond = (midFirst + (end - start) / 3); // 두 번째 구간의 중간 지점
        if(array[midFirst] == key)
            return midFirst;
        if(array[midSecond] == key)
            return midSecond;
        if(key < array[midFirst])
            return ternarySearch(array, start, midFirst-1, key);
        if(key > array[midSecond])
            return ternarySearch(array, midSecond+1, end, key);
        return ternarySearch(array, midFirst+1, midSecond-1, key);
    }
    return -1;
}

int main() {
    int n, searchKey, loc;
    cout << "Enter number of items: ";
    cin >> n;
    int arr[n]; // 크기 n인 배열 생성
    cout << "Enter items: " << endl;

    for(int i = 0; i< n; i++) {
        cin >> arr[i];
    }

    cout << "Enter search key to search in the list: ";
    cin >> searchKey;
    if((loc = ternarySearch(arr, 0, n, searchKey)) >= 0)
        cout << "Item found at location: " << loc << endl;
    else
        cout << "Item is not found in the list." << endl;
}

실행 결과

Enter number of items: 8
Enter items:
12 25 48 52 67 79 88 93
Enter search key to search in the list: 52
Item found at location: 3

동작 원리 요약

위 예제에서 배열 [12, 25, 48, 52, 67, 79, 88, 93]에서 키 값 52를 찾는 과정은 다음과 같습니다.

전체 범위에서 두 개의 중간 지점(midFirst, midSecond)을 계산합니다.
두 중간 지점의 값이 키와 일치하는지 먼저 확인합니다.
키가 첫 번째 중간값보다 작으면 왼쪽 구간을, 두 번째 중간값보다 크면 오른쪽 구간을 탐색합니다.
그 외의 경우에는 두 중간 지점 사이의 구간을 탐색 대상으로 좁힙니다.
범위가 더 이상 유효하지 않으면 -1을 반환하여 탐색 실패를 알립니다.

이처럼 삼항 검색은 매 단계마다 탐색 범위를 1/3로 줄여나가므로, 로그 시간 복잡도 O(log₃ n) 안에 키 값을 찾을 수 있습니다.