বাইনারী অনুসন্ধানের মতো, এটিও তালিকাগুলিকে উপ-তালিকায় বিভক্ত করে৷ এই পদ্ধতি দুটি মধ্যবর্তী মধ্য মান ব্যবহার করে তালিকাটিকে তিনটি ভাগে ভাগ করে। যেহেতু তালিকাগুলি আরও উপবিভাগে বিভক্ত, তাই এটি একটি মূল মান অনুসন্ধান করার সময় কমিয়ে দেয়৷
Ternary সার্চ টেকনিকের জটিলতা
- সময়ের জটিলতা:O(log3 n)
- স্পেস জটিলতা:O(1)
ইনপুট এবং আউটপুট
Input: A sorted list of data: 12 25 48 52 67 79 88 93 The search key 52 Output: Item found at location: 3
অ্যালগরিদম
ternarySearch(array, start, end, key)
ইনপুট - একটি সাজানো অ্যারে, শুরু এবং শেষ অবস্থান, এবং অনুসন্ধান কী
আউটপুট - চাবির অবস্থান (যদি পাওয়া যায়), অন্যথায় ভুল অবস্থান।
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
উদাহরণ
#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;
} আউটপুট
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
