In this article, we will implement Ternary Search algorithm and compare its performance with Binary Search.

**Prerequisite**: Binary Search

In Ternary Search, we divide our array into three parts (*by taking two mid*) and discard two-third of our search space at each iteration. So at first look it seems that ternary search might be faster than binary search as its time complexity should be O(log_{3}N) which is less than time complexity of binary search O(log_{2}N). Before we analyze the claim, let’s take a look at is C++ implementation first.

## 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 |
#include <iostream> using namespace std; // Ternary search algorithm to return the position of // target x in the array A of size N int TernarySearch(int arr[], int n, int x) { int low = 0, high = n - 1; while (low <= high) { int left_mid = low + (high - low) / 3; int right_mid = high - (high - low) / 3; // int left_mid = (2*low + high)/3; // int right_mid = (low + 2*high)/3; if (arr[left_mid] == x) return left_mid; else if (arr[right_mid] == x) return right_mid; else if (arr[left_mid] > x) high = left_mid - 1; else if (arr[right_mid] < x) low = right_mid + 1; else low = left_mid + 1, high = right_mid - 1; } return -1; } // Ternary Search vs Binary search int main() { int A[] = { 2, 5, 6, 8, 9, 10 }; int n = sizeof(A) / sizeof(A[0]); int target = 6; int index = TernarySearch(A, n, target); if (index != -1) cout << "Element found at index " << index; else cout << "Element not found in the array"; return 0; } |

`Output:`

Element found at index 2

As we can see, at each iteration ternary search makes atmost 4 comparisons as compared to binary search which only makes 2 comparisons. So,

For Binary search – T(n) = 2clog_{2}n + O(1)

For Ternary search – T(n) = 4clog_{3}n + O(1)

By applying simple mathematics, we can establish that the time taken by Ternary search is equal to 2log_{3}2 times the time taken Binary search algorithm.

Now since 2log_{3}2 > 1, we actually get *more* comparisons with ternary search.

So a ternary search will still gives the same asymptotic complexity O(log N) search time but adds complexity to the implementation. The same argument is valid for a quaternary search or k-nary search for any other higher order.

As pointed out by Oriba Desu in comments below, Ternary search can be used to find extremum (minimum or maximum) of a unimodal function.

**Thanks for reading.**

Please use ideone or C++ Shell or any other online compiler link to post code in comments.

Like us? Please spread the word and help us grow. Happy coding 🙂

## Leave a Reply

This article fails to mention that the two algorithms are used for different problems. Ternary search can be used to find min or max of a unimodal function.

Thanks Oriba. We have added this point to the post. Happy coding 🙂