Ternary Search Algorithm With Example

Ternary Search uses the principle of Divide And Conquer.

It is similar to Binary Search Algorithm. But here, we divide the sub-array into three parts rather than two parts. For this, we use two middle values mid1 and mid2.

mid1 = low + ( ( high - low ) / 3 )
mid2 = high – ( ( high - low ) / 3 )

where, low is the index of starting element of the sub-array to be searched, high is the index of last element of that sub-array.

After finding the values of mid1 and mid2, we compare key with the values of input_array[mid1] and input_array[mid2].

• If key == input_array[mid1], key is found at position mid1 of input_array.
• If key == input_array[mid2], key is found at position mid2 of input_array.
• If key < input_array[mid1], we need to search the key in the first part of the sub-array. So, high = mid1 - 1. Now the sub-array ends at mid1-1.
• If key > input_array[mid2], we need to search the key in the third part of the sub-array. So, low = mid2 + 1. Now the sub-array starts from mid2+1.
• If input_array[mid1] < key < input_array[mid2], we need to search the key in the second part of the sub-array. So, low = mid1 + 1 and high = mid2 - 1. Now the sub-array starts at mid1+1 and ends at mid2-1.

Note : At each stage, the sub-array is reduced to one third of its length.

In this way, during each stage we check the possible range in which the key can lie in the sub-array and minimize the sub-array.

Let us look at ternary search with an example:

Let input_array = {12,18,23,25,29,32,35,40,58,66} and key = 23

     

Advantage of Ternary Search:

During each comparison, 66% of the elements are eliminated from the sub-array.

Disadvantage of binary search:

This algorithm does not work if the input_array is not in sorted order.

Time Complexity : O(log₃N)
Space Complexity : O(1)

Ternary Search is efficient than Binary Search and Linear Search in terms of its Time Complexity.

C++ CODE FOR TERNARY SEARCH:

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int N,i,low,mid1,mid2,high,key,position=-1;
    cout << "Enter the length of array" << endl;
    cin >> N; // Taking length of array as input
    int input_array[N];
    cout << "Enter array elements in increasing order" << endl;
    for(i=0;i<N;i++) // loop to take array elements as input
    {
        cin >> input_array[i];
    }
    cout << "Enter the element to be searched" << endl;
    cin >> key; // taking key as input
    low=0; // initialising low to 0 because initially sub-array is the input_array
    high=N-1; // initialising high to N-1 because initially sub-array is the input_array
    while(low<=high) // the index of first element of sub-array is always less than or equal to the index of last element of sub-array
    {
        mid1 = low + (high - low)/3; // finding the value of mid1
        mid2 = high - (high - low)/3; // finding the value of mid2
        if(key==input_array[mid1]) // checking if key is equal to the array element at mid1
        {
            position = mid1; // if yes, storing the value of mid1 and stopping the search
            break;
        }
        else if(key==input_array[mid2]) // checking if key is equal to the array element at mid2
        {
            position = mid2; // if yes, storing the value of mid2 and stopping the search
            break;
        }
        else if(key < input_array[mid1]) // checking if key is less than array element at mid1
        {
            high = mid1 - 1; // if yes, sub-array ends at mid1-1
        }
        else if(key > input_array[mid2]) // checking if key is greater than array element at mid2
        {
            low = mid2 + 1; // if yes, sub-array starts from mid2+1
        }
        else
        {
            /* if the value of key is greater than array element at mid1 and less than array element at mid2, 
            sub-array starts at mid1+1 and ends at mid2-1 */
            low = mid1 + 1;
            high = mid2 - 1;
        }
    }
    if(position >= 0) // checking if position is greater or equal to zero
    {
        cout << "key found at index " << position << endl; // if yes, key is found at index position of input_array
    }
    else // if not, key is not found in input_array
    {
        cout << "key is not found in the array" << endl;
    }
    return 0;
}

 TESTCASE :

Enter the length of array
5
Enter array elements in increasing order
14 35 67 89 90
Enter the element to be searched
67
key found at index 2