This is pretty easy to solve for "worst case" and "average case" mathematically. But DigitalKitty's script makes it pretty easy to also empirically test. This isn't intended to be a replacement for mathematical proof, but rather, just a quick realworld example of how efficient the binarysearch algorithm is. For each of the items in the table below, a modified DigitalKitty script was run. The modification causes the script to search for random numbers ten times in each range, and then print the average number of guesses for those ten searches. In each case, the range is assumed to be "0 .. N".
So here are a few trial runs:
Range Average Guesses
10 2.5
100 6
1000 9
10000 13
100000 16.5
1000000 19.5 (That's a range of 1 million)
1000000000 29.5 (That range is 1 billion)
1000000000000 39 (The range is 1 trillion)
So this unscientific example shows that you can find one number hidden among a range of one trillion numbers, on average, after 39 guesses, using a binary search. Also, it should be noted that the larger the range, the smaller the standard deviation in number of guesses needed, as a percent of total guesses. A binary search is fairly stable; not very sensitive to the dataset.
If you were to bet someone you could guess their number between zero and 100 in less than ten guesses, you will most likely walk home with the money. But you'll really surprise someone if you can guess a one out of a trillion number in well under 50 guesses.
