Binary search: Difference between revisions
Content added Content deleted
m (→{{header|C}}: Dots after messages.) |
(→{{header|XPL0}}: Added.) |
||
Line 7,171: | Line 7,171: | ||
22 was found at index 1 of the array. |
22 was found at index 1 of the array. |
||
70 was not found in the array. |
70 was not found in the array. |
||
</pre> |
|||
=={{header|XPL0}}== |
|||
{{trans|C}} |
|||
{{works with|EXPL-32}} |
|||
<lang xpl0> |
|||
\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 |
|||
</lang> |
|||
{{out}} |
|||
<pre> |
|||
2 is at index 4. |
|||
5 is not found. |
|||
</pre> |
</pre> |
||