Binary search is a pretty neat (and tricky) concept. We have a sorted list of numbers, and we want to find out if it contains a particular number. We start by checking the middle number of the list (the median!). If the number we're looking for is higher then its in the second half of the list. If its lower then its in the first half of the list (if at all). Because it halfs the size of the list each time, it very quickly find the number even for large lists.
However its harder to implement than it sounds. This is famously evidenced by the first paper on the subject which demonstrated the algorithm in 1946. The first correct demonstration was in 1962. For 16 years this approach was known, documented and used, yet never once implemented correctly! There's more details on what can go wrong here.
The reason this crossed my mind was when Alex challenged me to guess his favourite number. Having established that it was between 1 and 100, we then proceeded to play higher or lower until I established it was in fact 95, which took me 7 guesses. It took me 7 guesses because I used a variant of binary search. The algorithm isn't exactly the same, but it uses the same divide and conquer approach. I realised that coding up this guessing game would be a neat introduction to these kinds of problem. You could get kids to just play the game, and see you long it takes them to develop an optimal strategy, then get them to write down how they would do it, before finally coding it.
Cutting to the chase... here's the code in Sniff.
make highGuess number
make lowGuess number
make guess number
when start
.set highGuess to 100
.set lowGuess to 0
.say "think of a number from 1 to 100"
.repeat until letter 1 of answer = "y"
..set guess to round ((highGuess +lowGuess )/2)
..ask join "is it " [guess] and wait
..if not letter 1 of answer="y"
...ask "is your number higher or lower" and wait
..if letter 1 of answer="h"
...set lowGuess to guess
..if letter 1 of answer="l"
...set highGuess to guess
We initially know that the the number is greater than 0 and less than or equal to 100. We then avererage our upper and lower limit, and round to the nearest whole number to produce our guess. Note that because we round up values ending in 0.5, if we've narrowed the range down to a gap of two (0...1, 99...100 or n...n+1) then the next number will be the upper of the two numbers. For that reason we need the range to be 0...100, rather than 1...100.
we then ask if our guess is correct (if it is then we're done!), and if not then if the secret number is higher or lower. We reduce our range based on the answer (strictly we should reduce highGuess to guess-1, but its not essential for the game - these are exactly the sort of things that make binary search tricky though).
The code will win the game within 7 guesses at most! Other strategies might get lucky (maybe I could guess that Lightning McQueen might have influenced Alex's choice of number), but in the long haul this is an optimal approach.
Having coded it to run on-screen, I figured it would be fun to run it on something more portable. The Arduino Multishield has been a handy toy the last few weeks: it has a numeric display, and three buttons so seemed ideal!
make highGuess number
make lowGuess number
make guess number
when start
.set buzzer to high
.
.forever
..set highGuess to 100
..set lowGuess to 0
..repeat until not button2
...set guess to round ((highGuess +lowGuess )/2)
...set message to [guess]
...if not button3
....set lowGuess to guess
....wait 0.1 secs
....wait until button3
...if not button1
....set highGuess to guess
....wait 0.1 secs
....wait until button1
Now we run forever, with button1 meaning lower, button3 meaning higher, and button2 for spot on (which resets the device).
The great thing of course is that though it takes 7 guesses to handle numbers up to 100, it only takes another 3 to handle numbers up to 100. How many guesses to handle numbers up to 1million?
From here you could easily go on more advanced divide and conquer algorithms, from binary search all the way through to quicksort, and FFT's.
No comments:
Post a Comment