60 lines
1.1 KiB
Plaintext
60 lines
1.1 KiB
Plaintext
\Binary search
|
|
code CrLf=9, IntOut=11, Text=12;
|
|
def Size = 10;
|
|
integer A, X, I;
|
|
|
|
function integer DoBinarySearch(A, N, X);
|
|
integer A, N, X;
|
|
integer L, H, M;
|
|
begin
|
|
L:= 0; H:= N - 1;
|
|
while L <= H do
|
|
begin
|
|
M:= L + (H - L) / 2;
|
|
case of
|
|
A(M) < X: L:= M + 1;
|
|
A(M) > X: H:= M - 1
|
|
other return M;
|
|
end;
|
|
return -1;
|
|
end;
|
|
|
|
function integer DoBinarySearchRec(A, X, L, H);
|
|
integer A, X, L, H;
|
|
integer M;
|
|
begin
|
|
if H < L then
|
|
return -1;
|
|
M:= L + (H - L) / 2;
|
|
case of
|
|
A(M) > X: return DoBinarySearchRec(A, X, L, M - 1);
|
|
A(M) < X: return DoBinarySearchRec(A, X, M + 1, H)
|
|
other return M
|
|
end;
|
|
|
|
procedure PrintResult(X, IndX);
|
|
integer X, IndX;
|
|
begin
|
|
IntOut(0, X);
|
|
if IndX >= 0 then
|
|
begin
|
|
Text(0, " is at index ");
|
|
IntOut(0, IndX);
|
|
Text(0, ".")
|
|
end
|
|
else
|
|
Text(0, " is not found.");
|
|
CrLf(0)
|
|
end;
|
|
|
|
begin
|
|
\Sorted data
|
|
A:= [-31, 0, 1, 2, 2, 4, 65, 83, 99, 782];
|
|
X:= 2;
|
|
I:= DoBinarySearch(A, Size, X);
|
|
PrintResult(X, I);
|
|
X:= 5;
|
|
I:= DoBinarySearchRec(A, X, 0, Size - 1);
|
|
PrintResult(X, I);
|
|
end
|