In this chapter we shall learn about below topics:
6.1 Introduction
6.2 Steps to perform Ternary search
6.3 Understanding Ternary Search with an example
6.4 Implementation of Ternary Search in C++
6.5 Output of the program
6.6 Time complexity of Ternary Search
6.1 Introduction:
Ternary Search is an divide and conquer algorithm.
6.2 Steps to perform Ternary search
Like in binary search, we always divide the array into 2 parts, in Ternary Search as the name suggests we divide the array into 3 parts.
So how do we calculate the 3 parts in ternary search?
To make the array into 3 parts, we need to get 2 mid elements. For that we use below formula:
1. mid1 = low + (high - low)/3
2. mid2 = high - (high - low)/3Then we use below calculation to check if the key element is present or not.
1. if x == mid1, then the key element has been found at the index of mid1
2. if x == mid2, then the key element has been found at the index of mid2
3. if x < mid1, then the key element is in the first part of the array.
4. if x > mid2, then the key element is in the third part of the array.
5. else the element is in the second part of the array.By doing so, we neglect 2/3rd part of the array and search the remaining 1/3 of the array for each iteration.
6.3 Understanding Ternary Search with an example
Consider the array as below:
[2, 3, 4, 5, 6, 7, 8, 10, 12, 14, 16, 25]
There are total of 12 elements, you need to find if the element 16 is present in the array or not.
So
mid_1 = 0 + [12 - 0 ]/ 3 = 4
mid_2 = 12 - [12 - 0 ]/ 3 = 12 - 4 = 8
So 3 parts of array will be:
{2, 3, 4, 5}
{6, 7, 8, 10}
{12, 14, 16, 25}
Now check if arr[mid_1] == 16? false
Now check if arr[mid_2] == 16? false
Now, element 16 is greater than arr[mid_2]. Hence we know that the element is in 3rd part of the array.
Now we need to concentrate on below array:
{12, 14, 16, 25}
Again calculate mid_1, mid_2
mid_1 = 9 + [12 - 9]/3 = 9 + 1 = 10
mid_2 = 12 - [12 - 9]/3 = 12 - 1 = 11
Now check if arr[mid_1] == 16? false
Now check if arr[mid_2] == 16? True
We have found our element.6.4. Implementation of Ternary Search in C++
#include<iostream>
using namespace std;
void ternary_search(int arr[], int low, int high, int x)
{
int mid1 = 0;
int mid2 = 0;
if (low <= high)
{
//calcuate mid1 value
mid1 = low + (high - low)/3;
//calculate mid2 value
mid2 = high - (high - low)/3;
//check if key element is at the index of mid1
if (x == arr[mid1])
{
cout<<"Key element is present"<<endl;
return;
}
//check if key element is at the index of mid1
if (x == arr[mid2])
{
cout<<"Key element is present"<<endl;
return;
}
//the key element is in the first part of the array.
if ( x < arr[mid1])
return ternary_search(arr, low, mid1-1, x);
//the key element is in the third part of the array.
else if ( x > arr[mid2])
return ternary_search(arr, mid2+1, high, x);
else
//the key element is in the second part of the array.
return ternary_search(arr, mid1+1, mid2-1, x);
}
cout<<"Key element is NOT present"<<endl;
return;
}
int main()
{
int arr[] = {1, 2, 3, 4, 5, 6, 7, 8};
int len = 8;
int key = 7;
ternary_search(arr, 0, len-1, key);
return 0;
}
6.5. Output of the program
Element found6.6. Time complexity of Ternary Search
Time complexity is O(log3 n).