48 lines
835 B
Plaintext
48 lines
835 B
Plaintext
10 REM Binary search
|
|
20 LET N = 10
|
|
30 FOR I = 1 TO N
|
|
40 READ A(I)
|
|
50 NEXT I
|
|
60 REM Sorted data
|
|
70 DATA -31, 0, 1, 2, 2, 4, 65, 83, 99, 782
|
|
80 LET X = 2
|
|
90 GOSUB 500
|
|
100 GOSUB 200
|
|
110 LET X = 5
|
|
120 GOSUB 500
|
|
130 GOSUB 200
|
|
140 END
|
|
|
|
190 REM Print result
|
|
200 PRINT X;
|
|
210 IF I1 < 0 THEN 240
|
|
220 PRINT "is at index"; I1; "."
|
|
230 RETURN
|
|
240 PRINT "is not found."
|
|
250 RETURN
|
|
|
|
460 REM Binary search algorithm
|
|
470 REM N - number of elements
|
|
480 REM X - searched element
|
|
490 REM Result: I1 - index of X
|
|
500 LET L = 0
|
|
510 LET H = N-1
|
|
520 LET F = 0
|
|
530 LET M = L
|
|
540 IF L > H THEN 650
|
|
550 IF F <> 0 THEN 650
|
|
560 LET M = L+INT((H-L)/2)
|
|
570 IF A(M) >= X THEN 600
|
|
580 LET L = M+1
|
|
590 GOTO 540
|
|
600 IF A(M) <= X THEN 630
|
|
610 LET H = M-1
|
|
620 GOTO 540
|
|
630 LET F = 1
|
|
640 GOTO 540
|
|
650 IF F = 0 THEN 680
|
|
660 LET I1 = M
|
|
670 RETURN
|
|
680 LET I1 = -1
|
|
690 RETURN
|