For binary search, what is the average number of comparisons needed to find a record in a file?
+2
A:
I'm assuming this is homework, so I'll provide a hint instead of a straight-up answer. I'll also assume you've been asked to find a relatively exact answer, not just a big-O answer.
Think of it this way: Every time you do a comparison, you halve the search space. If the search space is of size S, then the probability of finding the record on the next iteration is 1/S. If C denotes the number of comparisons, then P(find it on comparison C) = P(don't find it in < C comparisons) * P(find it on comparison C | don't find it in < C comparisons).
dsimcha
2010-03-09 03:29:24
Thanks, a big-O answer is meaningless. I think your answer won't help though because it's about probability. I don't need the probability I need the number.
Phenom
2010-03-09 03:51:57
But how would you calculate the average without using probability? The average is just the sum of all possible values of C, weighted by their probability. That said, I haven't fully worked out the math but I can tell it would be fairly messy if I did. This is a pretty evil problem, especially if your professor is a stickler for exact derivations as opposed to approximations.
dsimcha
2010-03-09 04:17:27
Also, my gut feeling is that you've misunderstood the problem and you should ask for clarification. Find out whether you really need an **exact** answer, and if not, whether it needs to only be asymptotically correct or correct for every N. If it has to be exact for every N, it's so horribly messy as to be virtually impossible.
dsimcha
2010-03-09 04:22:41