Binary search: Difference between revisions
→{{header|Picat}}
(→{{header|XPL0}}: Added.) |
|||
Line 5,075:
return $guess;
}</lang>
=={{header|Picat}}==
<lang Picat>go =>
A = [2, 4, 6, 8, 9],
TestValues = [2,1,8,10,9,5],
println("iterative:"),
foreach(Value in TestValues)
test(binary_search,A, Value)
end,
test(binary_search,[1,20,3,4], 5), % unsorted array
nl,
println("recursive:"),
foreach(Value in TestValues)
test(binary_search_rec,A, Value)
end,
test(binary_search_rec,[1,20,3,4], 5), % unsorted array
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.
% Iterative version
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.
% Recursive version
binary_search_rec(A, Value) = Ret =>
Ret = binary_search_rec(A,Value, 1, A.length).
binary_search_rec(A, _Value, _Low, _High) = -1, sort(A) != A => true.
binary_search_rec(_A, _Value, Low, High) = 0, High < Low => true.
binary_search_rec(A, Value, Low, High) = Mid =>
Mid1 = (Low + High) // 2,
if A[Mid1] > Value then
Mid1 := binary_search_rec(A, Value, Low, Mid1-1)
elseif A[Mid1] < Value then
Mid1 := binary_search_rec(A, Value, Mid1+1, High)
end,
Mid = Mid1.</lang>
Output:
<pre>iterative:
A: [2,4,6,8,9] Value:2 Ret: 1: The value 2 is found at position 1.
A: [2,4,6,8,9] Value:1 Ret: 0: The value 1 is not in the array.
A: [2,4,6,8,9] Value:8 Ret: 4: The value 8 is found at position 4.
A: [2,4,6,8,9] Value:10 Ret: 0: The value 10 is not in the array.
A: [2,4,6,8,9] Value:9 Ret: 5: The value 9 is found at position 5.
A: [2,4,6,8,9] Value:5 Ret: 0: The value 5 is not in the array.
A: [1,20,3,4] Value:5 Ret: -1: The array is not sorted.
recursive:
A: [2,4,6,8,9] Value:2 Ret: 1: The value 2 is found at position 1.
A: [2,4,6,8,9] Value:1 Ret: 0: The value 1 is not in the array.
A: [2,4,6,8,9] Value:8 Ret: 4: The value 8 is found at position 4.
A: [2,4,6,8,9] Value:10 Ret: 0: The value 10 is not in the array.
A: [2,4,6,8,9] Value:9 Ret: 5: The value 9 is found at position 5.
A: [2,4,6,8,9] Value:5 Ret: 0: The value 5 is not in the array.
A: [1,20,3,4] Value:5 Ret: -1: The array is not sorted.</pre>
=={{header|PicoLisp}}==
| |||