# Binary Search Vs Ternary Search

Shreya Deep
Last Updated: May 13, 2022

## Introduction

Binary search and ternary search are two very efficient searching algorithms used to find an element (key) in an array. Both are based on the divide and conquer policy.

In binary search, we keep dividing the sorted array into two halves (and determine which one has the key) until we find the element we’re searching for, whereas, in ternary search, we divide the array into three halves (and determine which one has the key) until we find the element we’re searching for. In this article, we’ll see the difference between these two based on their time complexity.

Before we dive in, let's brush up our skills in Binary Search with the following video.

## Analysis of the time complexity

Since in ternary search, we divide our array into three parts and discard the two-thirds of space at iteration each time, you might think that it's time complexity is log3(n) which is faster as compared to that of binary search which has a complexity of log2(n), if the size of the array is n.

But you’re in a delusion if you think so.

Let’s look at the code once to see what exactly is happening.

Input

Output

## Implementation of Ternary Search

Input

Output

We can observe from the above implementation that, for the array a[] = {2,5,6,8,9,10} and target  = 6, in the ternary search,

Whereas in the case of binary search,

So, ternary search makes 4 comparisons whereas, in binary search, we only make a maximum of 2 comparisons in each iteration.

In binary search, T1(n) = 2clog2(n) + O(1)  (c = constant)

In ternary search, T2(n) = 4clog3(n) + O(1)  (c=constant)

Thus, T2(n)~2*log3(2) * T1(n), implies that ternary search will make more comparisons and thus will have more time complexity.

Let’s move on to some frequently asked questions on binary search vs ternary search.

1. What is the time complexity of ternary search?
The time complexity of ternary search is O(log3 n).

2. Is binary search better than ternary search?
Yes, in terms of complexity, binary search is better than ternary search.

3. Is ternary search useful?
Ternary search is extremely useful in the case when the function can’t be differentiated easily. We can use it to find the extremum(minimum and maximum) of a function.

4. Is linear search better than binary search?
Binary search is more efficient than linear search; it has a time complexity of O(log n). The array must be in a sorted order for it to work.

5. What are the different searching algorithms?
Linear search, Binary search and ternary search are the three different searching algorithms.

## Key takeaways

In this article, we did the comparison between binary search and ternary search on the basis of their time complexity. If you clearly understood, move forward and learn about the top searching and sorting algorithms used.

These searching algorithms are frequently, very efficient and are asked in various coding contests as well as placements tests.

To practice problems on searching algorithms, Codestudio is a one-stop destination. This platform will help you acquire effective coding techniques and give you an overview of student interview experience in various product-based companies.

Happy Coding!