Algorithim

Question

The average number of comparisons made by binary search for an unsuccessful search in array A

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.

---

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

---

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

Answer 1

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 E_l)

considering unsuccessful keys = external nodes

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

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

                                           =  ( E_l ) / (I+1) answer

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 log₂n as what i said earlier... but this above method will give more exact and close solution rather than taking log..

 

---

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..

---

@minipanda : ok ok np ;l