Tìm kiếm ba phân (Ternary Search) - Thuật toán và ví dụ

Giống binary search, Ternary Search chia danh sách thành 3 phần bằng 2 giá trị mid trung gian. Do chia nhiều hơn, giảm thời gian tìm kiếm.

Độ phức tạp

• Thời gian: O(log₃ n)
• Không gian: O(1)

Đầu vào / Đầu ra

Input:  Sorted list: 12 25 48 52 67 79 88 93, key=52
Output: Item found at location: 3

Thuật toán

ternarySearch(array, start, end, key)
Begin
    if start <= end:
        midFirst  = start + (end - start) / 3
        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)
        else: return ternarySearch(array, midFirst+1, midSecond-1, key)
    else: return invalid location
End

Ví dụ C++

#include <iostream>
using namespace std;

int ternarySearch(int arr[], int start, int end, int key) {
    if(start <= end) {
        int midFirst = start + (end - start) / 3;
        int midSecond = midFirst + (end - start) / 3;
        if(arr[midFirst] == key) return midFirst;
        if(arr[midSecond] == key) return midSecond;
        if(key < arr[midFirst]) return ternarySearch(arr, start, midFirst-1, key);
        if(key > arr[midSecond]) return ternarySearch(arr, midSecond+1, end, key);
        return ternarySearch(arr, midFirst+1, midSecond-1, key);
    }
    return -1;
}

int main() {
    int n, key, loc;
    cout << "Enter number of items: "; cin >> n;
    int arr[n]; cout << "Enter items: " << endl;
    for(int i=0;i> arr[i];
    cout << "Enter search key: "; cin >> key;
    if((loc = ternarySearch(arr, 0, n, key)) >= 0)
        cout << "Item found at location: " << loc << endl;
    else
        cout << "Item not found." << endl;
}

Kết quả

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