Self doubt in Binary search Algo

Question

The average successful search time taken by binary search on a sorted array of $10$ items?

1. $2.6$
2. $2.7$
3. $2.8$
4. $2.9$

Answer is $2.9$

My doubt:- But when I am using $log_2n$ for $n = 10$ it is not equal to $2.9$, and $log_210 = 3.3219$ ?

Comments

ahwan is correct checkout his answer and uif still confused then ask your problem

---

It will be always less than or equal to ( log n) . What you were trying to find is a common abuse of asymptotic time complexities.

Answer 1

Here time means the average number of comparisions....
It is binary search.
Draw a binary search tree with 10 elements (Take any set of 10 numbers & draw a BST)
You will see number of nodes are ..
1 root .. then two nodes ...then 2 nodes from each ... at last 3 nodes in leaf..
1+ 2+ 4 + 3 = 10 you know.
So you may have to go through these heights to get the elements.
Average comparisions = ( 1*1 + 2*2 + 3*4 +  4*3  ) / 10    =    29/10  = 2.9

Comments

@Ahwan

can you clear this doubt of csazad2702. even i have the same doubt.

i mean the bst constructed depends on the way we insert the elements right?? but how can we get the bst as specified you? please clarify this

---

The doubt of cascade is obivious but if we observe that the binary search algorithm always will construct a binary tree corresponding to it such that before moving to next level it will always completely fill the previous level. Since if we notice the property we target the mid element always which will become the root thus dividing array into two equal parts. Example if 10 elements 5th is root (1-4) are in  LST and (6-10) in RST. Again in each child this invariant holds.

Thereby try to always construct full binary tree and calculate the cost then take average.

---

@Ahwan

I get your answer but I am confused that how did you decide that time means average number of comparisons and then do it through BST.

Please help I am lost a bit here.

Answer 2

The 10 items i1, i2, ..., i10 may be arranged in a binary search trees as in Fig below. To get i5, the number of comparision needed is 1; for i2, it is 2; for i8 it is 2; for i1 it is 3, and so on. The average is (1+(2+2) +(3+3+3+3)+(4+4+4))/10, i.e., 2.9.

Comments

@Angkit,The explanation that you've given is irrespective of the values that the binary search tree has. Am I right?This has got to do nothing with the values. The formula is applicable to all values such as character,float or integer?

---

Yes,The formula is applicable to all values such as character,float or integer

---

Even you take any set of values you will get the same tree which he drew.

Because the key point here is the array is sorted. As the array is sorted if you apply the Binary Search for each element then younwill get exactly same tree as in his explanation.