-
Notifications
You must be signed in to change notification settings - Fork 76
/
binary_search.pi
121 lines (96 loc) · 2.69 KB
/
binary_search.pi
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
/*
Binary search in Picat.
From http://rosettacode.org/wiki/Binary_search
"""
Given the starting point of a range, the ending point of a range, and the
"secret value", implement a binary search through a sorted integer array
for a certain number. Implementations can be recursive or iterative
(both if you can). Print out whether or not the number was in the array
afterwards. If it was, print the index also. The algorithms are as such
(from the wikipedia):
"""
Also see http://en.wikipedia.org/wiki/Binary_search
Model created by Hakan Kjellerstrand, hakank@gmail.com
See also my Picat page: http://www.hakank.org/picat/
*/
main => go.
go =>
A = [2, 4, 6, 8, 9],
println(A),
% println(binary_search(A, 2)),
test1(A,2),
test1(A, 1),
test1(A, 8),
test1(A, 10),
test1(A, 9),
test1(A, 5),
test1([1,20,3,4], 5), % not sorted array
println("recursive:"),
% println(binary_search2(A, 2)),
test2(A,2),
test2(A, 1),
test2(A, 8),
test2(A, 10),
test2(A, 9),
test2(A, 5),
test2([1,20,3,4], 5), % not sorted array
nl.
test1(A, Value) =>
Ret = binary_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.
test2(A, Value) =>
Ret = binary_search_rec(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.