Every Computer Science Professionals should know about Ternary Search

All of us know about the Binary search but the question is about what is the Ternary search? If you are in the field of computer science then you must have a question about that and you have a curiosity to knows about it.

So, Let’s Know about the Ternary Search.

Ternary Search is a Divide and Conquer Algorithm used to perform search operations in a Sorted Array.

This algorithm is similar to the BST(Binary Search Algorithm). In Binary Search we divided the array into two parts but in Ternary it divides the array into three different parts.

Let’s Check the Pseudo Code:-

We Can divide the array into three parts by taking mid1 and mid2 which can be calculated as shown below.

1 and r will be equal to 0 and N-1 respectively, where N = Length of the array.

mid1 = 1 + (r-1)/3
mid2 = r - (r-1)/3

Ternary Search itself state that the array is divided into 3 parts:-

First part = left(lower bound) to mid1

Second part = mid1 + 1 to mid2

Third part = mid2 +1 to right(upper bound)

Let’s Learn it with the example:–

Steps to perform Ternary Search –

1. First, we compare the key with the element at mid1. If found equal, we return mid1.
2. If not, then we compare the key with the element at mid2. If found equal, we return mid2.
3. If not, then we check whether the key is less than the element at mid1. If yes, then recur to the first part.
4. If not, then we check whether the key is greater than the element at mid2. If yes, then recur to the Third part.
5. If not, then we recur to the second(Middle) part.

Time Complexity :- O(Log3N)

Where , N = Number of elements in the array.

Note :- The array must be sorted in order to perform the Binary search or Ternary search operation.

Thank you All!!! Hope you find this useful.