The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+1 vote
225 views
Why to prefer binary search over ternary search?Can someone give recreance relation for ternary search,so that i can compare both
asked in Algorithms by Boss (24.3k points) | 225 views
+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

1 Answer

+3 votes

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

answered by (321 points)
edited by


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

37,162 questions
44,734 answers
127,403 comments
43,805 users