What is the ternary search?

Computer systems perform different search techniques to find any particular data. There are many search algorithms, and each is more optimal than the other, depending on conditions. We know that a binary search divides the array into two parts. The ternary search works the same but divides the array into three equal parts, as its name implies. Ternary search works only for the sorted data. In this Answer, we'll see discuss how the ternary search works.

Initially, the value of start is zero and is $n-1$ , where n is the total number of elements in the array. Let's see the steps we need to perform for the ternary search:

Compare the key element with mid1. If it is found, return mid1.
If not, compare the key element with mid2. If it i found, return mid2.
Compare the key element with mid1. If it is less, then recur to the first part.
Compare the key element with mid2. If it is greater, then recur to the third part. Otherwise, recur to the middle part.

Example

#include <iostream>
using namespace std;
// Function to perform Ternary Search
int ternarySearch(int start, int end, int key, int array[])  
{
    while (end >= start) {
        // Find the mid1 and mid2
        int mid1 = start + (end - start) / 3;
        int mid2 = end - (end - start) / 3;
        // Check if key is present at any mid
        if (array[mid1] == key) {
            return mid1;
        }
        if (array[mid2] == key) {
            return mid2;
        }
        //if not at mid
        if (key < array[mid1]) {
            // The key lies in between start and mid1
            end = mid1 - 1;
        }
        else if (key > array[mid2]) {
            // The key lies in between mid2 and end
            start = mid2 + 1;
        }
        else {
            // The key lies in between mid1 and mid2
            start = mid1 + 1;
            end = mid2 - 1;
        }
    }
    // Key not found
    return -1;
}  
// Driver code
int main()
{
    int start, end, index, key;
    int array[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10,11,12,13,14 };
    // Starting index
    start = 0;
    // length of array
    end = 14;
    // Key to be searched in the array
    key = 8;  
    // Search the key using ternarySearch
    index = ternarySearch(start,end, key, array);
    // Print the result
    cout << "Index of "<<key<<" is " << index << endl;
  
}

Explanation

Lines 4–9: We define a function, ternarySearch(), in which we perform a ternary search on a sorted array. In the while loop, we initialize two midpoints, mid1 and mid2 , to divide the array into three parts.
Lines 10–16: We check if the key is at any of the midpoints. If yes, we return that midpoint.
Lines 17–24: We check if the key is less than or greater than any midpoint. If it is smaller, we subtract 1 from mid1. Otherwise, we add 1 in mid2.
Lines 25–33: In the else part, we update the values of the midpoints if the key lies between them. In case the key is not found, we return -1.

The time complexity of the ternary search is $O(log_{3}n)$ , where n is the size of the array. The space complexity of the ternary search is $O(1)$ .

Note: The time complexity of the ternary search is better than the binary search, but the number of comparisons in ternary search makes it slower than binary search.

What is the ternary search?

Working

Example

Code

Explanation