Ternary Search vs Binary search

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(log3N) which is less than time complexity of binary search O(log2N). Before we analyze the claim, let’s take a look at its C and Java implementation first.


Download   Run Code


Download   Run Code


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,

Ternary Search vs Binary search complexity analysis

For Binary search – T(n) = 2clog2n + O(1)
For Ternary search – T(n) = 4clog3n + O(1)

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

Now since 2log32 > 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.

1 Star2 Stars3 Stars4 Stars5 Stars (1 votes, average: 5.00 out of 5)


Thanks for reading.

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂

Leave a Reply

newest oldest most voted
Notify of
Oriba Desu

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.


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)