"Searching Algorithms / Binary Trees" for QB Express #24
Written by Dean Menezes



Let's say you have a guess the number program where
the computer tries to find the human's number
(pseudo-code):

FOR i = 1 TO 31
 ask the user if their number is i
 if their number is i,
   print "I got it in"; i; "guesses";
   end
 end if
NEXT

Clearly, if the user's number is N, the program will
take N guesses to arrive at this result (max of 31
guesses).

See if you can make a more efficient algorithm.

                  16

        8                      24

   4        12           20         28
  / \       / \         /  \       /  \
 2    6   10   14    18    22    26    30
 /\   /\   /\   /\    /\    /\    /\    /\
1 3  5 7  9 11 13 15 17 19 21 23 25 27 29 31


More efficient algorithm using binary tree:

1. Start at the top of the binary tree
2. Ask the user if their number is (current number)
3. If their number is the current number then stop
4. Else, ask them if their number is higher or lower
than the current number
5. If higher, go right on the tree. If lower, go left
on the tree.
6. Go to step 2

This will need a maximum of 5 guesses, making it much
more efficent than the first method.

Here is an implementation of QBASIC:

DECLARE SUB logic (low!, high!, numturns!)
CLS
PRINT "Think of an integer x such that 1 "; CHR$(243);
" x "; CHR$(243); " 31"
PRINT "Press any key when ready."
WHILE INKEY$ = ""
 'Dummy press any key routine
WEND
CALL logic(1, 31, 0)

SUB logic (low, high, numturns)
 num = (low + high) / 2
 DO
   PRINT "Is your number"; num
   INPUT answer$
   IF UCASE$(LEFT$(answer$, 1)) = "Y" THEN PRINT "I
got it in"; numturns; "turns": EXIT SUB
   IF UCASE$(LEFT$(answer$, 1)) = "N" THEN EXIT DO
   PRINT "Please answer the question."
 LOOP
 DO
   PRINT "Is your number higher or lower than"; num
   INPUT answer$
   IF UCASE$(LEFT$(answer$, 1)) = "H" THEN CALL
logic(num + 1, high, numturns + 1): EXIT SUB
   IF UCASE$(LEFT$(answer$, 1)) = "L" THEN CALL
logic(low, num - 1, numturns + 1): EXIT SUB
   PRINT "Please answer the question."
 LOOP
END SUB

Here is another example of where a binary tree could
make a program more efficient.

INPUT "num? ", num
INPUT "accuracy? ", acc
FOR i = 0 TO num STEP acc
 IF i * i >= num THEN PRINT i: END
NEXT

This is a program to find the square root of a number
to a certain accuracy. It does this by increminting a
variable until the varialbe squared is greater than
the number.

Can you write a faster version of this program?

Here is the fast version:

INPUT "num? ", num
INPUT "accuracy? ", acc
g1 = 1
DO
 g2 = num / g1
 IF ABS(g2 - g1) < acc THEN PRINT "val is between";
g1; "and"; g2: END
 g1 = (g1 + g2) / 2
LOOP

Here's how the fast program works:
1. it starts out with this range:
0 ......... n
2. then is gets an initial guess (always picks 1 in
example). the range is now
g0 .... 1/g0
3. then it picks the average of the two bounds as the
new guess
g1 .. 1/g1
4. it repeats step 3 until the range is within the
desired accuracy (small range = more accurate).