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

## Java

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) = 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 votes, average: 5.00 out of 5)

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 🙂