The average successful search time taken by binary search on a sorted array of $10$ items?
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$ ?
@Shubhansh Do not remember it as a formula. Just take 10 elements. Put it in a BST. & search for each elements. I am doing the same. Yes. If it is at height 3, then to reach that element I need to go through other two parent nodes. Is not it? So height is multiplied.
Now I got it finally, thanks @Ahwan @Tauhin Gangwar.
It was really silly doubt now I come to know. Thanks all.
@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 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.
64.3k questions
77.9k answers
244k comments
80.0k users