71 lines
1.2 KiB
Plaintext
71 lines
1.2 KiB
Plaintext
MODULE BinarySearch;
|
|
|
|
FROM STextIO IMPORT
|
|
WriteLn, WriteString;
|
|
FROM SWholeIO IMPORT
|
|
WriteInt;
|
|
|
|
TYPE
|
|
TArray = ARRAY [0 .. 9] OF INTEGER;
|
|
|
|
CONST
|
|
A = TArray{-31, 0, 1, 2, 2, 4, 65, 83, 99, 782}; (* Sorted data *)
|
|
|
|
VAR
|
|
X: INTEGER;
|
|
|
|
PROCEDURE DoBinarySearch(A: ARRAY OF INTEGER; X: INTEGER): INTEGER;
|
|
VAR
|
|
L, H, M: INTEGER;
|
|
BEGIN
|
|
L := 0; H := HIGH(A);
|
|
WHILE L <= H DO
|
|
M := L + (H - L) / 2;
|
|
IF A[M] < X THEN
|
|
L := M + 1
|
|
ELSIF A[M] > X THEN
|
|
H := M - 1
|
|
ELSE
|
|
RETURN M
|
|
END
|
|
END;
|
|
RETURN -1
|
|
END DoBinarySearch;
|
|
|
|
PROCEDURE DoBinarySearchRec(A: ARRAY OF INTEGER; X, L, H: INTEGER): INTEGER;
|
|
VAR
|
|
M: INTEGER;
|
|
BEGIN
|
|
IF H < L THEN
|
|
RETURN -1
|
|
END;
|
|
M := L + (H - L) / 2;
|
|
IF A[M] > X THEN
|
|
RETURN DoBinarySearchRec(A, X, L, M - 1)
|
|
ELSIF A[M] < X THEN
|
|
RETURN DoBinarySearchRec(A, X, M + 1, H)
|
|
ELSE
|
|
RETURN M
|
|
END
|
|
END DoBinarySearchRec;
|
|
|
|
PROCEDURE WriteResult(X, IndX: INTEGER);
|
|
BEGIN
|
|
WriteInt(X, 1);
|
|
IF IndX >= 0 THEN
|
|
WriteString(" is at index ");
|
|
WriteInt(IndX, 1);
|
|
WriteString(".")
|
|
ELSE
|
|
WriteString(" is not found.")
|
|
END;
|
|
WriteLn
|
|
END WriteResult;
|
|
|
|
BEGIN
|
|
X := 2;
|
|
WriteResult(X, DoBinarySearch(A, X));
|
|
X := 5;
|
|
WriteResult(X, DoBinarySearchRec(A, X, 0, HIGH(A)));
|
|
END BinarySearch.
|