Binary search program (+ quotes glitch, interfaces)

[gerard@dugdill.com]

Two things please:

• For a study project, I had to create a program where the computer guessed a number between 1 and 100 based on binary search. I paste it below at the very bottom. It’s nearly there but I think not quite perfect. It could perhaps be reworked better from first principles.

One thing I noticed is for example when I type in 33 as the input number for the computer to find, at one point the two previous computer guesses are 31 and 35, so the next one hopefully would have been 33, but it goes to 32 instead. I guess it’s a tiny element in the program that makes it not ideal.

I just wanted the program to find the number in seven attempts rather than eight. Maybe eight is the realistic maximum. Maybe it’s OK.

I hope I am not breaking the “spirit” of the forum by asking for precise feedback on a program. Sorry if so.

If there are no suggestions I will probably move on. I am only a beginner so am actually quite pleased that I have made this attempt. I am still working through all the tutorial notes etc (as well as trying to learn some other program basics at the same time, web, java, python… not to mention AI )

• One other point. When I type in quote marks from word into SDLIDE, it doesn’t like quote marks, eg PRINT “test” gives:

PRINT ENVELOPEANDCOUNTtestENVELOPEANDDEG

I find the interface fiddly to work with cf word for example.

At least though you can edit lines with SDLIDE compared with the BBC emulator (national computer history centre, which doesn’t seem to let you edit lines at all + fussy about copy and paste etc)

Sorry for the hassle, thanks for the help. kr

PROGRAM CODE:

10 CLS
20 LET MAX = 100 : LET MIN = 0 : LET RANGE = MAX - MIN
30 PRINT "GIVE ME A NUMBER BETWEEN 1 AND 100"
40 INPUT N : H$= ""
50 PRINT "OK, HERE IT IS - "; N : PRINT
60 ATTEMPT = 1 : PRINT "NOW LET ME GUESS IT IN 8 GOs. IS IT " : PRINT
70 LET G = ((RANGE / 2) + MIN) : GUESS = INT(G) : IF H$="H" GUESS = GUESS+1
80 PRINT GUESS;"? Y or N -"; " ATTEMPT NO. ";ATTEMPT
90 INPUT A$
100 IF A$="Y" THEN PRINT "GREAT" ELSE IF A$ = "N" THEN GOTO 105 ELSE GOTO 80
101 END
105 PRINT "IS IT HIGHER OR LOWER, H or L?" : INPUT H$
107 IF H$="H" MIN = MIN+(RANGE/2) ELSE IF H$= "L" MAX = MAX-(RANGE/2)
108 RANGE = MAX - MIN
109 ATTEMPT=ATTEMPT+1 : GOTO 70

[Richard Russell]

• For a study project, I had to create a program where the computer guessed a number between 1 and 100 based on binary search. I paste it below at the very bottom. It’s nearly there but I think not quite perfect. It could perhaps be reworked better from first principles.

Did you base your binary search on the flowchart given in the manual here? As far as I am aware, that algorithm if implemented accurately should work.

• One other point. When I type in quote marks from word into SDLIDE, it doesn’t like quote marks, eg PRINT “test” gives:

Indeed, Word (and some other word processors) uses 'smart quotes' by default, that is the left quote is automatically changed from " to “ and the right quote is automatically changed from " to ”.

This, not surprisingly, confuses SDLIDE. There may be some way of switching off smart quotes in Word, but I don't use it myself.

[gerard@dugdill.com]

Thanks. I am not sure I did to be honest. I just dived it and went for it so to speak.

OK on quotes. If the system is surprised...

I received another suggestion externally, which seems to work.

I guess I will look back at the algorithm when I reach that point in the manual.

Many thanks for your help,

Gerard

[DDRM]

The higher/lower code on 107 could be easier?

Why don't you simply:
a) If the guess is too low, set min to guess + 1
b) if the guess is too high, set max to guess - 1?

I suspect, but haven't worked through except for the first case, that what you are doing sets the min/max to guess (not one either side of it), which will worsen the performance a little.

I note also that your initial min = 0, but you are looking for a number between 1 and 100, so shouldn't it be 1? That means you'll need to adjust the calculation of range, and probably the guess.

2^ = 128, so you are right, you should always be able to get it in 7 goes.

D

[Richard Russell]

Why don't you simply:
a) If the guess is too low, set min to guess + 1
b) if the guess is too high, set max to guess - 1?

I've not studied the OP's code (it contains GOTOs, so I refuse to look at it!) but when I've coded a binary search it has been necessary for at least one of min and max be set equal to guess, not one away.

The reason is that you don't want to add a test for equality inside the loop, because this adds an overhead to every iteration which is wasteful. Rather you only want a single conditional test inside the loop, and that means if the guess is correct the new range must contain it.

Of course this does mean that the loop will always execute the maximum number of iterations, rather than exit prematurely when the guess is correct, but statistically you win on overall performance (I think) because an additional comparison is expensive..

[Ric]

Evening Gerard,
just thought id have a go at your challange and this was the result, there are no error traps, but it works in 7 guesses or less every time

Code: Select all

    
      INPUT "Please input a number between 1 and 100 ";num%
      min% = 1
      max% = 100
      atempt% = 0
      REPEAT
        PRINT "Your number is ";num%
        guess% = (min% + max%) / 2
        PRINT "My guess is ";guess%
        IF num% < guess% THEN max% = guess% ELSE min% = guess%
        atempt% += 1
      UNTIL num% = guess%
      PRINT "Did it in ";atempt%;" goes"

Hope this helps

[Richard Russell]

INPUT "Please input a number between 1 and 100 ";num%

"Between" here is somewhat ambiguous, but assuming it means from 1 to 100 inclusive your code doesn't work correctly if 100 is entered.