61 lines
877 B
Plaintext
61 lines
877 B
Plaintext
REM Binary search
|
|
DIM A(10)
|
|
REM Sorted data
|
|
DATA -31, 0, 1, 2, 2, 4, 65, 83, 99, 782
|
|
FOR I = 0 TO 9
|
|
READ A(I)
|
|
NEXT I
|
|
N = 10
|
|
X = 2
|
|
GOSUB DoBinarySearch:
|
|
GOSUB PrintResult:
|
|
X = 5
|
|
GOSUB DoBinarySearch:
|
|
GOSUB PrintResult:
|
|
END
|
|
|
|
PrintResult:
|
|
PRINT X;
|
|
IF IndX >= 0 THEN
|
|
PRINT " is at index ";
|
|
PRINT IndX;
|
|
PRINT "."
|
|
ELSE
|
|
PRINT " is not found."
|
|
ENDIF
|
|
RETURN
|
|
|
|
DoBinarySearch:
|
|
REM Binary search algorithm
|
|
REM N - number of elements
|
|
REM X - searched element
|
|
REM Result: IndX - index of X
|
|
L = 0
|
|
H = N - 1
|
|
Found = 0
|
|
Loop:
|
|
IF L > H THEN AfterLoop:
|
|
IF Found <> 0 THEN AfterLoop:
|
|
REM (L <= H) and (Found = 0)
|
|
M = H - L
|
|
M = M / 2
|
|
M = L + M
|
|
REM So, M = L + (H - L) / 2
|
|
IF A(M) < X THEN
|
|
L = M + 1
|
|
ELSE
|
|
IF A(M) > X THEN
|
|
H = M - 1
|
|
ELSE
|
|
Found = 1
|
|
ENDIF
|
|
ENDIF
|
|
GOTO Loop:
|
|
AfterLoop:
|
|
IF Found = 0 THEN
|
|
IndX = -1
|
|
ELSE
|
|
IndX = M
|
|
ENDIF
|
|
RETURN
|