Ternary search in C++

In this tutorial, we will learn about the ternary search and its implementation in C++.

Ternary Search: It is a divide and conquer algorithm that is used to find an element in an array. It is similar to a binary search algorithm. In this algorithm, we divide the array into 3 parts as shown in the figure.

ternary search in C++

Formulas to calculate m1 and m2:

m1 = l + (r – l) / 3

m2 = r – (r – l) / 3

Steps of ternary search algorithm:

  1. Compare key with the elements at the m1 index and m2 index. If the key gets matched with the element at m1 index then return m1 and if it gets matched with the element at m2 index then return m2.
  2. Check If the key is less than the element at the m1 index. If yes, then recursively call the function to check if the key is present in between l and m1-1 index.
  3. If the key is greater than the element at the m2 index then recursively call the function to check if the key is present in between m2+1 and r index.
  4. Otherwise recursively call the function to check if the key is present in between m1+1 and m2-1 index.
  5. Return -1 if the element is not present in the array.

(*Note: To perform ternary search elements of the array must be sorted in ascending order.)

Program to implement Ternary Search in C++

#include<iostream>
using namespace std; 
  
int ternary_search(int arr[], int l, int r, int key) 
{ 
    if (l<=r) 
    { 
    	/* calculating m1 and m2 */
        int m1 = l + (r - l) / 3; 
        int m2 = r - (r - l) / 3; 
  
        /* Check if the key is present at m1 or m2 index */
        if (arr[m1]==key)  
        { 
            return m1; 
        }
     
        if (arr[m2]==key) 
        { 
            return m2; 
        } 
  
        if (key < arr[m1])  
        { 
  
            /* search key in between l and m1-1 index */
            return ternary_search(arr, l, m1 - 1, key); 
        } 
        else if (key > arr[m2])  
        { 
  
            /* search key in between m2+1 and r index */
            return ternary_search(arr, m2 + 1, r, key); 
        } 
        else
        { 
  
            /* search key in between m1+1 and m2-1 index */
            return ternary_search(arr, m1 + 1, m2 - 1, key); 
        } 
    } 
  
    /* if the key is not present in the array */
    return -1; 
} 
  
int main() 
{ 
  int n, i, key, res;
    cout<<"Enter the no. of elements: ";
    cin>>n;
    
    /* declaring arr of n size */
    int arr[n];
    
    /* Enter elements in sorted(ascending) order */
    cout<<"Enter elements: ";
    for(i=0;i<n;i++)
    {
    	cin>>arr[i];
  }
    
    cout<<"\nEnter element to search: ";
  cin>>key;
  
    res=ternary_search(arr, 0, n-1, key); 
  
  if(res==-1)
    cout<<"\nElement doesn't exist..!!";
  else
    cout<<"\nElement is present at index "<<res;
    
  return 0;
}

Input/Output:

Enter the no. of elements: 7
Enter elements: -4 0 3 7 11 14 17

Enter element to search: 11

Element is present at index 4

Time Complexity

O(log3 n), where n is the no. of elements in the array.

You may also read:

  1. How to create a CSV file in C++
  2. Kruskal’s algorithm in C++

Leave a Reply

Your email address will not be published. Required fields are marked *