in Algorithms retagged by
1,218 views
0 votes
0 votes
The average number of comparisons made by binary search for an unsuccessful search in array A
in Algorithms retagged by
1.2k views

4 Comments

@arya no it's not like that... You are applying bs on path length... Which is false..

.

@magma : mine answer is wrong... And yours too seems to be because you should be using a binary search tree and they have asked for unsuccessful search...

.

I have got the answer just trying to frame it.
0
0

hmm understood brother ,

I just want to say that avg case of Binary search is different from the normal case I hope you know

but yes time complexity is  floor (logn)

you can check this

http://sce.uhcl.edu/yang/teaching/csci3333spring2011/Average%20case%20analysis%20of%20binary%20search.pdf

0
0
its wrong solution bro :/ check i have posted @magma
0
0

1 Answer

1 vote
1 vote

let us consider binary search tree for array elements ={10,8,15,3,12}.

consider the diagram :

black circle = elements present in array

red circle = elements not present in Array ( unsuccessful search keys).

.

now suppose we search for key 1 :

we will first search at root =10 (absent). then we will drop dowm next level as (1<10) and goto left tree. value of new node = 8( not equal to 1 and 1<8) we will drop down new node where key = 3 (not equal to 1 ).

now here we know that 3 does not have any child node so we will stop here (in other words we know that array is empty)

#comparisons = 3. 

similarly for other keys :   

keys(unsuccessful search) #comparisons
1 3
4 3
9 2
11 3
13 3
16 2

overall comparison = 3+3+2+3+3+2 (or total external node length El)

considering unsuccessful keys = external nodes

#number of candidates = 6 (or number of internal nodes(I) +1).

so average comparisons = total comparisons/ #keys(US)

                                           =  ( E) / (I+1) answer

by

4 Comments

If the array is sorted like {3,8,10,12,15} .

 

keys  comparisons
1 3
4 3
9 2
11 2
13 3
16 3

 

@minipanda it will too have the same result if we store the keys as u said ..

even if we construct any other binary search tree structure it will give the same result..

yes it will be close to log2n as what i said earlier... but this above method will give more exact and close solution rather than taking log..

 

1
1
Yes @arvin for the external nodes nothing changes for your diagram.. I just asked to get cleared about the relation b/w Binary search and Binary search tree..
1
1
@minipanda : ok ok np ;l
0
0

Related questions