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 one-third or 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 lie between O(log_{3}N) and O(log_{2}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.

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; } // main function 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 🙂