Logo

Programming-Idioms

  • Lisp
  • Go
  • JS
  • Pascal

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.

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
}

Iterative algorithm.
It does not always return the smallest possible index.
You may implement this for any element type T that is ordered.
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
}

This uses the standard library generic-purpose sort.Search. Read the documentation carefully.
It returns the smallest matching index.
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
}

If the elements have type int, then use standard library's sort.SearchInts.
It returns the smallest matching index.
import "slices"
func binarySearch(a []T, x T) int {
	if i, ok := slices.BinarySearch(a, x); ok {
		return i
	} else {
		return -1
	}
}

This generic func slices.BinarySearch works for all slice types
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)
}

x | 0 removes the bit of x after the decimal.
This would be easier if JavaScript had more builtins for list processing.
function BinarySearch(X: Integer; A: Array of Integer): Integer;
var
  L, R, I, Cur, answer: Integer;
  isIt :boolean;
begin
  isIt := false;
  answer := -1;
  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
	answer := i;  {cur;}
	isIt := true;
    end;
    if (X > Cur) then
       L := I + 1
    else
      R := I - 1
  end;
  BinarySearch := answer;
end;

the index of the array is i;
Cur is the value of A[i]; but we
search the index i
function binarySearch (x: integer; a: array of integer): integer;
var  L, R, M: integer;  // left, right, middle
begin
  if Length(a)=0 then Exit(-1);
  L := Low (a);
  R := High(a);
  while (L <= R) do begin
    M := (L + R) div 2;
    if (x = a[M]) then Exit(M);  // found x in a
    if (x > a[M]) 
    then L := Succ(M)
    else R := Pred(M);
  end;
  Exit(-1) // did not found x in a
end;
#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;
}

Check for an empty vector up front, otherwise size() will return an unsigned 0, and subtracting 1 will be a big number!
New implementation...
< > ⌨
programming-idioms.org 
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
}
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 []int, x int) int {
	i := sort.SearchInts(a, x)
	if i < len(a) && a[i] == x {
		return i
	}
	return -1
}
func binarySearch(a []T, x T) int {
	if i, ok := slices.BinarySearch(a, x); ok {
		return i
	} else {
		return -1
	}
}
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)
}
function BinarySearch(X: Integer; A: Array of Integer): Integer;
var
  L, R, I, Cur, answer: Integer;
  isIt :boolean;
begin
  isIt := false;
  answer := -1;
  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
	answer := i;  {cur;}
	isIt := true;
    end;
    if (X > Cur) then
       L := I + 1
    else
      R := I - 1
  end;
  BinarySearch := answer;
end;
function binarySearch (x: integer; a: array of integer): integer;
var  L, R, M: integer;  // left, right, middle
begin
  if Length(a)=0 then Exit(-1);
  L := Low (a);
  R := High(a);
  while (L <= R) do begin
    M := (L + R) div 2;
    if (x = a[M]) then Exit(M);  // found x in a
    if (x > a[M]) 
    then L := Succ(M)
    else R := Pred(M);
  end;
  Exit(-1) // did not found x in a
end;
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;
}

public static int binarySearch<T>(T[] a, T x)
{
    var result = Array.BinarySearch<T>(a, x);
    return result >= 0 ? result : -1;
}
public static int binarySearch<T>(List<T> a, T x)
{
    var result = a.BinarySearch(x);
    return result >= 0 ? result : -1;
}
long binarySearch(long[] a, long x) {
    long result = a.assumeSorted.lowerBound(x).length;
    if (result == a.length || a[result] != x)
        return -1;
    return result;
}
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.
   integer function binarysearch(a,x) result(l)
      integer,intent(in)::a(:)
      integer,intent(in)::x
      integer::r,mid
      l=1
      r=size(a)
      do while(l<=r)
         mid=l+(r-l)/2;
         if(a(mid)==x)then
            l=mid
            return
         end if
         if(a(mid)<x)then
            l=mid+1;
         else 
            r=mid-1;
         end if
      end do
      l=-1
   end function binarysearch

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
static int binarySearch(final int[] arr, final int key) {
    final int index = Arrays.binarySearch(arr, key);
    return index < 0 ? - 1 : index;
}
int i = binarySearch(a, x);
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;
}
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;
    }
}

# 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;

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);