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 its C and Java 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 |
#include <stdio.h> // 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 algorithm int main(void) { int A[] = { 2, 5, 6, 8, 9, 10 }; int target = 6; int n = sizeof(A) / sizeof(A[0]); int index = TernarySearch(A, n, target); if (index != -1) printf("Element found at index %d", index); else printf("Element not found in the array"); return 0; } |

## Java

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 |
class TernarySearch { public static int ternarySearch(int[] A, int x) { int left = 0, right = A.length - 1; while (left <= right) { int leftMid = left + (right - left) / 3; int rightMid = right - (right - left) / 3; // int leftMid = (2*left + right) / 3; // int rightMid = (left + 2*right) / 3; if (A[leftMid] == x) { return leftMid; } else if (A[rightMid] == x) { return rightMid; } else if (A[leftMid] > x) { right = leftMid - 1; } else if (A[rightMid] < x) { left = rightMid + 1; } else { left = leftMid + 1; right = rightMid - 1; } } return -1; } public static void main(String[] args) { int[] A = { 2, 5, 6, 8, 9, 10 }; int key = 6; int index = ternarySearch(A, key); if (index != -1) { System.out.println("Element found at index " + index); } else { System.out.println("Element not found in the array"); } } } |

`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 🙂

Equality check could be removed. It is quite usual to search not exact match, but first element that is greater or equal.

But other problem arose: cache efficiency. Average memory acces for ternary search per loop round is 1.66, and 1.66/log(3) slightly larger than 1/log(2)