टर्नरी सर्च

बाइनरी सर्च की तरह, यह भी लिस्ट को सब-लिस्ट में विभाजित करता है। यह प्रक्रिया दो इंटरमीडिएट मिड मानों का उपयोग करके लिस्ट को तीन भागों में विभाजित करती है। चूंकि लिस्ट अधिक उप-विभाजनों में विभाजित होती है, इसलिए यह की मान खोजने का समय कम करती है।

टर्नरी सर्च तकनीक की जटिलता

समय जटिलता: O(log₃ n)
स्पेस जटिलता: O(1)

इनपुट और आउटपुट

इनपुट: सॉर्टेड डेटा की सूची: 12 25 48 52 67 79 88 93 खोज कुंजी 52 आउटपुट: आइटम स्थान पर मिला: 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); //पहले और दूसरे ब्लॉक का मिड       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