# Idiom #124 Binary search for a value in sorted array

Write the function binarySearch which returns the index of an element having the value x in the sorted array a, or -1 if no such element exists.

``````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)
}``````
``#include <vector>``
``````template<typename T>
int binarySearch(const std::vector<T> &a, const T &x)
{
if(a.size() == 0) return -1;

size_t lower = 0;
size_t upper = a.size() - 1;

while(lower <= upper)
{
auto mid = lower + (upper-lower) / 2;

if(x == a[mid])
{
return (int)mid;
}
else if(x > a[mid])
{
lower = mid + 1;
}
else
{
upper = mid - 1;
}
}

return -1;
}
``````
``using System;``
``````public static int binarySearch<T>(T[] a, T x)
{
var result = Array.BinarySearch<T>(a, x);
return result >= 0 ? result : -1;
}``````
``using System.Collections.Generic;``
``````public static int binarySearch<T>(List<T> a, T x)
{
var result = a.BinarySearch(x);
return result >= 0 ? result : -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;
}``````
``import 'package:collection/collection.dart';``
``a.binarySearch(x);``
``````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 - First) 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.``````
``import "golang.org/x/exp/slices"``
``````func binarySearch(a []T, x T) int {
if i, ok := slices.BinarySearch(a, x); ok {
return i
} else {
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
}``````
``````func binarySearch(a []T, x T) int {
imin, imax := 0, len(a)-1
for imin <= imax {
imid := imin + (imax-imin) / 2
switch {
case a[imid] == x:
return imid
case a[imid] < x:
imin = imid + 1
default:
imax = imid - 1
}
}
return -1
}``````
``````binSearch :: Ord a => a -> [a] -> Maybe Int
binSearch _ [] = Nothing
binSearch t l = let n = div (length l) 2
(a, m:b) = splitAt n l in
if t < m then binSearch t a
else if t > m then aux (binSearch t b)
else Just n where
aux :: Maybe Int -> Maybe Int
aux (Just x) = Just (x+n+1)
aux _ = Nothing``````
``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;
}``````
``````function binarySearch(array \$a, \$x)
{
\$imin = 0;
\$imax = count(\$a) - 1;
while (\$imin <= \$imax) {
\$imid = (int)floor(\$imin + (\$imax-\$imin) / 2);
if (\$a[\$imid] === \$x) {
return \$imid;
}
if (\$a[\$imid] < \$x) {
\$imin = \$imid + 1;
} else {
\$imax = \$imid - 1;
}
}
return -1;
}``````
``````function BinarySearch(X: Integer; A: Array of Integer): Integer;
var
L, R, I, Cur, answer: Integer;
isIt :boolean;
begin
isIt := false;
if Length(A) = 0 then Exit;
L := Low(A);
R := High(A);
while ((L <= R) AND (isIt = false)) do
begin
I := L + ((R - L) div 2);
Cur := A[I];
if (X = Cur) then begin
isIt := true;
end;
if (X > Cur) then
L := I + 1
else
R := I - 1
end;
end;``````
``use 5.020;``
``````sub binary_search {
my (\$x, \$A, \$lo, \$hi) = @_;
\$lo //= 0;
\$hi //= @\$A;
my \$mid = int(\$lo + (\$hi - \$lo) / 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;
}
}
``````
``use List::BinarySearch qw( binsearch  );``
``````# Some ordered arrays to search within.
@num_array =   ( 100, 200, 300, 400, 500 );
@str_array = qw( Bach Beethoven Brahms Mozart );

# Find the lowest index of a matching element.

\$index = binsearch {\$a <=> \$b} 300, @num_array;
\$index = binsearch {\$a cmp \$b} 'Mozart', @str_array;
``````
``import bisect``
``````def binarySearch(a, x):
i = bisect.bisect_left(a, x)
return i if i != len(a) and a[i] == x else -1
``````
``````def binary_search(a, el)
a.bsearch_index{|x| x == el} || -1
end``````
``a.binary_search(&x).unwrap_or(-1);``

programming-idioms.org