Explain what is Ternary Search?

Technology CommunityCategory: SearchingExplain what is Ternary Search?
VietMX Staff asked 3 years ago

Like linear search and binary search, ternary search is a searching technique that is used to determine the position of a specific value in an array. In binary search, the sorted array is divided into two parts while in ternary search, it is divided into 3 parts and then you determine in which part the element exists.

Ternary search, like binary search, is a divide-and-conquer algorithm. It is mandatory for the array (in which you will search for an element) to be sorted before you begin the search. In a ternary search, there is a possibility (33.33% chance, actually) that you can eliminate 2/3 of the list, but there is an even greater chance (66.66%) that you will only eliminate 1/3 of the list.

Ternary search has a lesser number of iterations than Binary Search but Ternary search also leads to more comparisons.

Average number of comparisons:

    in ternary search = ((1/3)*1 + (2/3)*2) * ln(n)/ln(3) ~ 1.517*ln(n)
    in binary search  =                   1 * ln(n)/ln(2) ~ 1.443*ln(n).

Worst number of comparisons:

    in ternary search = 2 * ln(n)/ln(3) ~ 1.820*ln(n)
    in binary search  = 1 * ln(n)/ln(2) ~ 1.443*ln(n).
Implementation
int ternary_search(int l,int r, int x)
{
    if(r>=l)
    {
        int mid1 = l + (r-l)/3;
        int mid2 = r -  (r-l)/3;
        if(ar[mid1] == x)
            return mid1;
        if(ar[mid2] == x)
            return mid2;
        if(x<ar[mid1])
            return ternary_search(l,mid1-1,x);
        else if(x>ar[mid2])
            return ternary_search(mid2+1,r,x);
        else
            return ternary_search(mid1+1,mid2-1,x);

    }
    return -1;
}