45 lines
994 B
Text
45 lines
994 B
Text
go =>
|
|
A = [2, 4, 6, 8, 9],
|
|
TestValues = [2,1,8,10,9,5],
|
|
|
|
foreach(Value in TestValues)
|
|
test(binary_search,A, Value)
|
|
end,
|
|
test(binary_search,[1,20,3,4], 5),
|
|
nl.
|
|
|
|
% Test with binary search predicate Search
|
|
test(Search,A,Value) =>
|
|
Ret = apply(Search,A,Value),
|
|
printf("A: %w Value:%d Ret: %d: ", A, Value, Ret),
|
|
if Ret == -1 then
|
|
println("The array is not sorted.")
|
|
elseif Ret == 0 then
|
|
printf("The value %d is not in the array.\n", Value)
|
|
else
|
|
printf("The value %d is found at position %d.\n", Value, Ret)
|
|
end.
|
|
|
|
binary_search(A, Value) = V =>
|
|
V1 = 0,
|
|
% we want a sorted array
|
|
if not sort(A) == A then
|
|
V1 := -1
|
|
else
|
|
Low = 1,
|
|
High = A.length,
|
|
Mid = 1,
|
|
Found = 0,
|
|
while (Found == 0, Low <= High)
|
|
Mid := (Low + High) // 2,
|
|
if A[Mid] > Value then
|
|
High := Mid - 1
|
|
elseif A[Mid] < Value then
|
|
Low := Mid + 1
|
|
else
|
|
V1 := Mid,
|
|
Found := 1
|
|
end
|
|
end
|
|
end,
|
|
V = V1.
|