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.