Tuesday, October 15, 2019

Published 10:01 PM by with 0 comment

Can Hints Make a Binary Search Faster?

You need to guess a number between 1 and 100. You are told if your guess is too high or too low. Does it help if you are also told when your guess is within 5 of the answer?
It might not be obvious, but this general problem is a binary search. To show the basic algorithm, imagine the number is 71. A good general approach should be:
  • start at the middle ((100 + 1) / 2, round down, so 50)
  • find out it's low
  • update your lowest point to guess + 1, so 51
  • find middle again ((100 + 51)/2, round down, so 75)
  • find out it's too high
  • update your highest point to guess - 1, so 74
  • find middle again ((74 + 51)/2, round down, so 62
  • keep doing this until you guess correctly
How many guesses will that take on average? Simulating this for all values between 1 and 100, I get ~5.8 guesses. The most common number of guesses is 7. This makes sense because 100 is between 2^6 (64) and 2^7 (128). The distribution of guesses needed if you play the game for all values between 1 and 100 is below:



Now...what if you're told when you're within 5 of the target? Repeat the example again:

  • start at the middle ((100 + 1) / 2, round down, so 50)
  • find out it's low
  • update your lowest point to guess + 1, so 51
  • find middle again ((100 + 51)/2, round down, so 75)
  • find out it's too high but is within 5 of the target
  • update your highest point to guess - 1, so 74
  • update your lowest point to guess - 5, so 70
  • find middle again ((74 + 70)/2, so 72
  • keep doing this until you guess correctly
This seems faster. Simulating this, I get ~4.9 guesses. The distribution of guesses needed if you play the game for all values between 1 and 100 is below:



There is probably some way to derive this directly but nothing came to mind. It's faster overall though.

One more thing...what hint is most valuable? Within 20? Within 10? Within 5? Below is the average guesses required vs warning range for values from 1 to 100 and from 1 to 1000:



Not sure where else to go with this so stopping here...






      edit

0 comments:

Post a Comment