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 is C++ implementation first.

C++

Download   Run Code

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,

  complexity
 

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.

 
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

Notify of
avatar
Sort by:   newest | oldest | most voted
Oriba Desu
Guest
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.

wpDiscuz