50 lines
990 B
Plaintext
50 lines
990 B
Plaintext
100 REM Binary search
|
|
110 HOME : REM 110 CLS for Chipmunk Basic, MSX Basic, QBAsic and Quite BASIC
|
|
111 REM REMOVE line 110 for Minimal BASIC
|
|
120 DIM a(10)
|
|
130 LET n = 10
|
|
140 FOR j = 1 TO n
|
|
150 READ a(j)
|
|
160 NEXT j
|
|
170 REM Sorted data
|
|
180 DATA -31,0,1,2,2,4,65,83,99,782
|
|
190 LET x = 2
|
|
200 GOSUB 440
|
|
210 GOSUB 310
|
|
220 LET x = 5
|
|
230 GOSUB 440
|
|
240 GOSUB 310
|
|
250 GOTO 720
|
|
300 REM Print result
|
|
310 PRINT x;
|
|
320 IF i < 0 THEN 350
|
|
330 PRINT " is at index "; i; "."
|
|
340 RETURN
|
|
350 PRINT " is not found."
|
|
360 RETURN
|
|
400 REM Binary search algorithm
|
|
410 REM N - number of elements
|
|
420 REM X - searched element
|
|
430 REM Result: I - index of X
|
|
440 LET l = 0
|
|
450 LET h = n - 1
|
|
460 LET f = 0
|
|
470 LET m = l
|
|
480 IF l > h THEN 590
|
|
490 IF f <> 0 THEN 590
|
|
500 LET m = l + INT((h - l) / 2)
|
|
510 IF a(m) >= x THEN 540
|
|
520 LET l = m + 1
|
|
530 GOTO 480
|
|
540 IF a(m) <= x THEN 570
|
|
550 LET h = m - 1
|
|
560 GOTO 480
|
|
570 LET f = 1
|
|
580 GOTO 480
|
|
590 IF f = 0 THEN 700
|
|
600 LET i = m
|
|
610 RETURN
|
|
700 LET i = -1
|
|
710 RETURN
|
|
720 END
|