টার্নারি সার্চ (Ternary Search)

বাইনারি সার্চের মতো, এটি লিস্টকে সাব-লিস্টে ভাগ করে। এই প্রসিডিউর দুইটি ইন্টারমিডিয়েট মিড ভ্যালু ব্যবহার করে লিস্টকে তিনটি অংশে ভাগ করে। যেহেতু লিস্টগুলো আরও বেশি সাবডিভিশনে ভাগ হয়, তাই সার্চ কী খুঁজে পেতে সময় কমে।

টার্নারি সার্চ টেকনিকের কমপ্লেক্সিটি

• টাইম কমপ্লেক্সিটি: O(log₃ 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)
Input - An sorted array, start and end location, and the search key
Output - location of the key (if found), otherwise wrong location.
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 
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> 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