24 lines
727 B
Text
24 lines
727 B
Text
10 REM Binary search
|
|
20 DIM A(10)
|
|
30 N% = 10
|
|
40 FOR I% = 0 TO 9: READ A(I%): NEXT I%
|
|
50 REM Sorted data
|
|
60 DATA -31, 0, 1, 2, 2, 4, 65, 83, 99, 782
|
|
70 X = 2: GOSUB 500
|
|
80 GOSUB 200
|
|
90 X = 5: GOSUB 500
|
|
100 GOSUB 200
|
|
110 END
|
|
190 REM Print result
|
|
200 PRINT X;
|
|
210 IF INDX% >= 0 THEN PRINT "is at index"; STR$(INDX%);"." ELSE PRINT "is not found."
|
|
220 RETURN
|
|
480 REM Binary search algorithm
|
|
490 REM N% - number of elements; X - searched element; Result: INDX% - index of X
|
|
500 L% = 0: H% = N% - 1: FOUND% = 0
|
|
510 WHILE (L% <= H%) AND NOT FOUND%
|
|
520 M% = L% + (H% - L%) \ 2
|
|
530 IF A(M%) < X THEN L% = M% + 1 ELSE IF A(M%) > X THEN H% = M% - 1 ELSE FOUND% = -1
|
|
540 WEND
|
|
550 IF FOUND% = 0 THEN INDX% = -1 ELSE INDX% = M%
|
|
560 RETURN
|