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 worst case should be O(log3N) which is less than worst case of binary search O(log2N). Let’s take a look at is implementation first.

 
C++ implementation –
 

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.

 
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 🙂