+1 vote
376 views
Why to prefer binary search over ternary search?Can someone give recreance relation for ternary search,so that i can compare both
+1
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

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)=log2n+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.log3n +!
Now if you compare these two by changing base of logs as 2.log3n=  (2 / log23) * log2n and you can verify that  (2 / log23)>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

edited by

1