Giống như tìm kiếm nhị phân, nó cũng tách các danh sách thành các danh sách con. Thủ tục này chia danh sách thành ba phần bằng cách sử dụng hai giá trị giữa trung gian. Vì danh sách được chia thành nhiều phần nhỏ hơn, do đó, nó làm giảm thời gian tìm kiếm giá trị khóa.
Sự phức tạp của Kỹ thuật tìm kiếm bậc ba
- Độ phức tạp về thời gian:O (log3 n)
- Độ phức tạp của không gian:O (1)
Đầu vào và Đầu ra
Input: A sorted list of data: 12 25 48 52 67 79 88 93 The search key 52 Output: Item found at location: 3
Thuật toán
ternarySearch(array, start, end, key)
Đầu vào - Một mảng được sắp xếp, vị trí bắt đầu và kết thúc, và phím tìm kiếm
Đầu ra - vị trí của chìa khóa (nếu được tìm thấy), nếu không thì sai vị trí.
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, midFirst+1, end, key) else call ternarySearch(array, midFirst+1, midSecond-1, key) else return invalid location End
Ví dụ
#include<iostream>
using namespace std;
int ternarySearch(int array[], int start, int end, int key) {
if(start <= end) {
int midFirst = (start + (end - start) /3); //mid of first and second block
int midSecond = (midFirst + (end - start) /3); //mid of first and second block
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]; //create an array of size 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;
} Đầu ra
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