Guess My Number Game

[Andrea Griffini]

On Sat, 15 May 2004 15:58:22 +0200, Heiko Wundram <heikowu at ceosg.de>
wrote:

Not really python related, but...

>On average, the shortest possible runtime (and also a deterministic runtime of 
>O(log2(high-low))) will be achieved if you use interval walking.
>
>Thus:
>
>number = 64
>low = 1
>high = 100
>while low <> high:
>	med = (low+high)//2
>	tries += 1
>	if med == number:
>		print "I guessed your number:", med
>	elif med < number:
>		if med == low:
>			print "I guessed your number:", med+1
>			low = med+1
>		else:
>			low = med
>	else:
>		high = med
>print "I needed", tries, "tries."

This bisection algorithm is bad. On average it will require
about 0.5 more steps than necessary. A better one is...

  def dico2(low,high,guess):
    while low < high:
      t = (low + high)//2
      g = guess(t)
      if g == 0:
        return t
      elif g == -1:
        low = t+1
      else:
        high = t-1
    return low

supposing that guess(x) returns -1, 0 or 1 depending
if the number is too low, correct or too high.

If you find yourself handling special cases in a
bisection algorithm (e.g. your test "if med==low")
then you can be quite sure there's a better way.

HTH
Andrea