Binary Search

Question

for binary search in an array of n elements the average number of searches is $\left \lfloor \log_{2}n \right \rfloor$ or $\left \lceil \log_{2}n \right \rceil$ ?

Comments

@shaik sir, I can't say right now, working on it. I will post.

---

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

Here one very important thing is considered that is

each element in the array requires different number of iterations in the binary search before it is found.

 

Please check this one.

 

---

@MiNiPanda, My approach also same which they follows... i agree it is log n but specifically floor....

i will add my version as answer.

Answer 1

Note: please check Shaik sir answer, you will get clear understanding. Because I can't say ceil or floor

Answer 2

let there are 15 elements

 

	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
value at the	i+010	i+092	i+432	i+487	i+532	i+576	i+623	i+654	i+655	i+709	i+713	i+717	i+786	i+876	i+901
no.of comparissions	4	3	4	2 ( finds at 2nd comparission)	4	3	4	1 ( finds at 1st comparission)	4	3	4	2 ( finds at 2nd comparission)	4	3	4

 

Avg.case = ∑ ( probability for j^th index * no.of comparissions for j^th index )

               = ( P(j=1) * no.of comparissions for value at (1) ) + ( P(j=2) * no.of comparissions for value at (2) ) +....+ ( P(j=15) * no.of comparissions for value at (15) )

probability of j^th index = $\frac{1}{n}$  (due to equal probability)

Avg.case = P(j) * ( ∑ ( no.of comparissions for j^th index ) )

              = $\frac{1}{15}$  * ( 2⁰ * 1 + 2¹ * 2 + 2² * 3 + 2³ *4  ) =  $\frac{1}{15}$  * ( 1+4+12+32  ) =  $\frac{1}{15}$  * ( 49) -----> which gives 3.2

i can't decide it is floor or ceil

 

let take no.of elements 11

	1	2	3	4	5	6	7	8	9	10	11
value at the	i+010	i+092	i+432	i+487	i+532	i+576	i+623	i+654	i+655	i+709	i+713
no.of comparissions	3	4	2 ( finds at 2nd comparission)	3	4	1 ( finds at 1st comparission)	3	4	2 ( finds at 2nd comparission)	3	4

 

Avg.case = ∑ ( probability for j^th index * no.of comparissions for j^th index )

               = ( P(j=1) * no.of comparissions for value at (1) ) + ( P(j=2) * no.of comparissions for value at (2) ) +....+ ( P(j=11) * no.of comparissions for value at (15) )

probability of j^th index = $\frac{1}{n}$  (due to equal probability)

Avg.case = P(j) * ( ∑ ( no.of comparissions for j^th index ) )

              = $\frac{1}{11}$  * ( 2⁰ * 1 + 2¹ * 2 + 2² * 3 + 2² *4  ) =  $\frac{1}{11}$  * ( 1+4+12+16  ) =  $\frac{1}{11}$  * ( 33 ) -----> which gives 3

but if we take ⌈ log₂ 11 ⌉ = 4 ===>  if we take ⌊ log₂ 11 ⌋  = 3

 

( it is my version on taking floor, may be i am wrong, please comment the correct reason if you think i did wrong )

Comments

Satisfied

Answer 3

I'm getting floor value. pls tell me if my approach is wrong

Comments

you did right thing by asking this doubt, these type of questions required discussion.

---

:)

---

@Rishav Kumar Singh,

i also feel the same

Answer 4

Ceeling of log2n