Coders Packet

Ternary Search(find an element or key in array) in C++

By Bharat Pandey

Hello Friends, Right now we are going to learn how to write a source code on Ternary Search in C++. Ternary Search Time Complexity is better than Binary Search.

Ternary Search is an Extended Version Of Binary Search. In ternary search, we divide the array into three parts remember binary search where we divide the array into two parts.

So, the first question that comes to our mind is how to divide the array into three parts? 

We can divide the array into three parts by taking mid1 and mid2 which can be calculated as shown below. Initially, left and right be equal to 0 and Size-1 respectively.

mid1 = left + (right-left)/3

mid2 =  right + (right-left)/3

=========

I will show you how to approach this algorithm through an example.

Example:

Input:

Given: Arr[] = {10 , 20 , 30 , 40 , 50 ,60 ,70}

size = 7

key = 40 

Solution:

step 1: Compute mid1 and mid2

mid1 = 2; mid2 = 4

step 2: Compare key first with mid1 than mid2.

if key found on any mid return mid.

Arr[mid1] is 30  is not equal to 40.

Arr[mid2] is 50 is not equal to 40.

step 3: check for the key lies in which part?

40 is greater than 30 and 40 is smaller than 50. So the key lies in the middle part of an array.

left = mid1+1 is  3.

right = mid2-1 is 3;

step 4: again compute mid1 and mid2.

mid1 = 3.

mid2 = 3.

step 5: compare key first with mid1 than mid2.

Arr[3] is  40 is equal to 40.

The Key is found on Index 3.

=========

Note: The solution is iterative.  The exit condition is when the left is greater than the right. 

=========

Algorithm:

step 1: First we check the left is not greater than the right. If we found True go to step2 else return false and print the key is not found.

step2: Compute mid1 and mid2 and go to step 3.

step 3: First, we compare the key with the element at mid1. if found equal, we return mid1 else go to step 4.

step 4: we compare the key with the element at mid2. if found equal, we return mid2 else go to step 5.

step 5: we check whether the key is less than the element at mid1. if yes then change right = mid1-1 and go to step 1 else go to step 6.

step 6: we check whether the key is greater than the element at mid2. if yes then change left = mid2+1 and go to step 1 else go to step 7.

step 7: left = mid1+1 and right = mid2-1 and go to step 1.

=========

Complexity Of Ternary Search:

Time Complexity: O(log3(N))

Space Complexity: O(1)

Download Complete Code

Comments

No comments yet