On an average, how many times would you have to flip over your City's Phone Book to locate a specific name/address?
Assume the phone book has 1000 pages, and you want to achieve at least 80% confidence.
2006-06-09 11:55:48 · 5 answers · asked by Anonymous in Science & Mathematics ➔ Mathematics
Well 2^9 = 512, so using a binary sort you should be able to find any address after flipping a maximum of 9 pages. I assume that you can open the book up and see 2 pages at once, by the way!
2 pages would be found after 1 flip
4 pages would be found after exactly 2 flips
8 pages would be found after exactly 3 flips
16 pages would be found after exactly 4 flips
32...5
64...6
128...7
256...8
512...9
Add these all up and you have 1022 pages found in no more than 9 flips.
The average depth would be a weighted average of the pages. So 50% of the pages would require a depth-9 search, 25% would require depth-8, 12.5% would require depth-7, etc.
If you add up this weighted average you find that the average depth is around 8. On an average you would need to flip the page 8 times.
Of course this assumes a perfect binary search and other factors that wouldn't be true in real life, but that might be the answer you were looking for.
2006-06-09 12:27:48 · answer #1 · answered by Puzzling 7 · 2⤊ 0⤋
2
2016-08-14 13:35:33 · answer #2 · answered by Roger 3 · 0⤊ 0⤋
Thrice.
Use Binary Sorting
2006-06-09 12:02:16 · answer #3 · answered by Raj 2 · 0⤊ 0⤋
twice
2006-06-09 11:59:05 · answer #4 · answered by dirtee diamondz 3 · 0⤊ 0⤋
how stupid is that question.i mean really!
2006-06-09 12:02:39 · answer #5 · answered by Anonymous · 0⤊ 0⤋