Trinary Search Algorithm

Tri-nary search algorithm is a simple and natural modification of binary search with triple-interval search or logarithmic search. It compares three elements in the first ( initial , middle and last position ) to finds the position of a target value within a sorted array. Unlike binary search algorithm which compares and finds the position of a target value within a sorted array by half-interval search or logarithmic search.
Benefit of Trinary Algo to Binary are

1. Fast comparism of the first and last of the target value

Example : Suppose we have 1 – 1,000,000 and we are looking for 1,000,000

Binary Algo will take four or more comparism to locate the target value  ,  trinary search algo return 1,000,000 in the first search , because the algo know the last and the first index position value ,
and also imagine we are looking for 999,999

it takes binary algo three or more steps to locate 999,999 , whereas it takes trinary algo two steps to locate 999,999
How ? After when trinary algo check 999,999  not to be in the initial first , last and middle index , it then compares 999,999 to the middle value (499,999) which then start searching from 500,000 to the last value – 1 i.e 1,000,000 – 1 = 999,999

trinary will also compare the middle value of 999,999 to 500,000 ( = 749,999 )

i.e trinary algo will only search values between

500,000 -749,999 – 999,999

the last value is our TARGET KEY , meaning trinary algo will need not to take futher steps unlike binary algo

2016-12-22-at-16-01-45

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Create a free website or blog at WordPress.com.

Up ↑

%d bloggers like this: