Programming-Idioms

Implementation

Be concise.

Be useful.

All contributions dictatorially edited by webmasters to match personal tastes.

Please try to avoid dependencies to third-party libraries and frameworks.

Implementation edit is for fixing errors and enhancing with metadata.

Instead of changing the code of the snippet, consider creating another Haskell implementation.

Other implementations
```func binarySearch(a []T, x T) int {
imin, imax := 0, len(a)-1
for imin <= imax {
imid := (imin + imax) / 2
switch {
case a[imid] == x:
return imid
case a[imid] < x:
imin = imid + 1
default:
imax = imid - 1
}
}
return -1
}```
`import "sort"`
```func binarySearch(a []int, x int) int {
i := sort.SearchInts(a, x)
if i < len(a) && a[i] == x {
return i
}
return -1
}```
`import "sort"`
```func binarySearch(a []T, x T) int {
f := func(i int) bool { return a[i] >= x }
i := sort.Search(len(a), f)
if i < len(a) && a[i] == x {
return i
}
return -1
}```
```import std.range;
import std.algorithm;```
```long binarySearch(long[] a, long x) {
long result = a.assumeSorted.lowerBound(x).length;
if (result == a.length || a[result] != x)
return -1;
return result;
}```
```function BinarySearch(X: Integer; A: Array of Integer): Integer;
var
L, R, I, Cur: Integer;
begin
Result := -1;
if Length(A) = 0 then Exit;
L := Low(A);
R := High(A);
while (L <= R) do
begin
I := L + (R - L) div 2;
Cur := A[I];
if (X = Cur) then Exit(I);
if (X > Cur) then
L := I + 1
else
R := I - 1;
end;
end;```
```def binarySearch(ar, el)
res = ar.bsearch{|x| x == el}
res ? res : -1
end```
```def binary_search(a, el)
a.bsearch_index{|x| x == el} || -1
end```
`import bisect`
```def binarySearch(a, x):
i = bisect.bisect_left(a, x)
return i if i != len(a) and a[i] == x else -1
```
`a.binary_search(&x).unwrap_or(-1);`
```bsearch([], _) -> -1;
bsearch([H|_T], X) when X < H -> -1;
bsearch(List, X) ->
bsearch(List, X, 0, length(List)).

bsearch(_List, _X, First, Last) when Last < First -> -1;
bsearch(List, X, First, Last) ->
Middle = (First + Last) div 2,
Item = lists:nth(Middle, List),
case Item of
X -> Middle;
_Less when X < Item -> bsearch(List, X, First, Middle);
_More -> bsearch(List, X, Middle + 1, Last)
end.```
```function binarySearch(a, x, i = 0) {
if (a.length === 0) return -1
const half = (a.length / 2) | 0
return (a[half] === x) ?
i + half :
(a[half] > x) ?
binarySearch(a.slice(0, half), x, i) :
binarySearch(a.slice(half + 1), x, half + i + 1)
}```
`import java.util.arrays;`
```static int binarySearch(final int[] arr, final int key) {
final int index = Arrays.binarySearch(arr, key);
return index < 0 ? - 1 : index;
}```
`use 5.020;`
```sub binary_search {
my (\$x, \$A, \$lo, \$hi) = @_;
\$lo //= 0;
\$hi //= @\$A;
my \$mid = int((\$lo + \$hi) / 2);
for (\$x cmp \$A->[\$mid]) {
use experimental 'switch';
return \$mid when 0;
return -1 if 1 == \$hi - \$lo;
return binary_search(\$x, \$A, \$lo, \$mid) when -1;
return binary_search(\$x, \$A, \$mid, \$hi) when 1;
}
}
```