## 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:

1 2 |
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.

1 2 3 4 5 |
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++

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 |
#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:

1 |
Element found |

The time complexity of the algorithm will be O(log3 n) at worst case. Where n is the number of elements.