practical searches
Saturday, 10 June 2006 07:48 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
miriam_eMany of us who got into computers in the "old days" are familiar with the term "binary search". It is a great way of finding something in as few steps as possible.
It's the best solution for that game where one person picks a number between 0 and 1000, and the other bets that they can guess it in 10 or less tries, given only the clues "higher" or "lower". It is simple: just add or subtract ever diminishing halves depending on whether the answer is higher or lower. It works best with powers of two, so the maximum starting point for 10 guesses is actually 1,024. The amounts added or subtracted each time in that case are 512, 128, 64, 32, 16, 8, 4, 2, 1.
It can be truly mind-boggling, for instance you can, without fail, guess a number between 0 and a million in 20 or less tries.
This has a lot of practical uses. I installed a lot of software on my niece's Palm computer, maybe 30 programs. Unfortunately one of the programs is crashing the machine at odd times. How do you track down the culprit in as few operations as possible? A binary search.
Remove half of the programs and see if the Palm still crashes. If it doesn't then we know the problem is in one of the uninstalled ones. Re-install half of those. See if it crashes. If it does then uninstall half those most recently re-installed. See if it crashes... etc. For 32 programs it should take no more than 5 steps.
Neat huh?
It's the best solution for that game where one person picks a number between 0 and 1000, and the other bets that they can guess it in 10 or less tries, given only the clues "higher" or "lower". It is simple: just add or subtract ever diminishing halves depending on whether the answer is higher or lower. It works best with powers of two, so the maximum starting point for 10 guesses is actually 1,024. The amounts added or subtracted each time in that case are 512, 128, 64, 32, 16, 8, 4, 2, 1.
It can be truly mind-boggling, for instance you can, without fail, guess a number between 0 and a million in 20 or less tries.
This has a lot of practical uses. I installed a lot of software on my niece's Palm computer, maybe 30 programs. Unfortunately one of the programs is crashing the machine at odd times. How do you track down the culprit in as few operations as possible? A binary search.
Remove half of the programs and see if the Palm still crashes. If it doesn't then we know the problem is in one of the uninstalled ones. Re-install half of those. See if it crashes. If it does then uninstall half those most recently re-installed. See if it crashes... etc. For 32 programs it should take no more than 5 steps.
Neat huh?