Algorithms :- Binary search vs ternary search

Question

Why to prefer binary search over ternary search?Can someone give recreance relation for ternary search,so that i can compare both

Comments

In binary search we're dividing an array into 2 parts whereas, in ternary search, we're going to divide the same array into 3 parts. so, in each step we've to accomplish one extra step or an extra comparison.

That's why we prefer binary search over ternary search

Answer 1

When we are talking about better one we are minimizing the no of comparisons required  in worst case which can be best expressed by setting up recurrences and solving since these algo's are recursive in nature

For binary search :- T(n)=T(n/2)+1                   //at each stage problem is divided into half and
                                                                           one comparison for choosing the half
Solving for closed form expression for T(n) using repeated substitution with T(1)=1 as base T(n)=log₂n+1

in Ternary search :- T(n)=T(n/3)+2                   //at each stage problem is reduced to 1/3rd size
                                                                           but # of comparisons at each stage is 2
and again solving closed form by repeated substitution would yield T(n)=2.log₃n +!
Now if you compare these two by changing base of logs as 2.log₃n=  (2 / log₂3) * log₂n and you can verify that  (2 / log₂3)>1 

The same argument can be used to compare worst case # of comparisons to show that dividing in half is best possible split.

An intuitive argument for this might be that if we can repeatedly think about the decreasing log base factor and always get better results with (k+1)-ary search then k-ary search but clearly if we keep doing this and hit n-ary search then it is equivalent to doing a linear search with # of comparisons as n-1 . So at some point the overheads increase so much that the decreasing log base factor no longer helps , As by the maths above that happens for k=2

Answer 2

The recurrence relation for binary search is 

T(n) = T(n/2) + 2,  T(1) = 1

The recurrence relation for ternary search is 

 T(n) = T(n/3) + 4, T(1) = 1

Time Complexity for Binary search = 2clog2n + O(1)
Time Complexity for Ternary search = 4clog3n + O(1)

Therefore, the comparison of Ternary and Binary Searches boils down the comparison of expressions 2Log3n and Log2n . The value of 2Log3n can be written as (2 / Log23) * Log2n . Since the value of (2 / Log23) is more than one, Ternary Search does more comparisons than Binary Search in worst case.

Comments

It should be T(n)=T(n/3)+3