Introduction:
Ternary Search is an divide and conquer algorithm.
Explanation of the algorithm:
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:
mid1 = low + (high - low)/3 mid2 = high - (high - low)/3
Then we use below calculation to check if the key element is present or not.
if x == mid1, then the key element has been found at the index of mid1 if x == mid2, then the key element has been found at the index of mid2 if x < mid1, then the key element is in the first part of the array. if x > mid2, then the key element is in the third part of the array. 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.
Understanding of Ternary search with help of 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.
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; }
Output:
Element found
The time complexity of the algorithm will be O(log3 n) at worst case. Where n is the number of elements.
Further Reading: