Logo

Programming-Idioms

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.
New implementation

Be concise.

Be useful.

All contributions dictatorially edited by webmasters to match personal tastes.

Please do not paste any copyright violating material.

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

Other implementations
#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.Collections.Generic;
public static int binarySearch<T>(List<T> a, T x)
{
    var result = a.BinarySearch(x);
    return result >= 0 ? result : -1;
}
using System;
public static int binarySearch<T>(T[] a, T x)
{
    var result = Array.BinarySearch<T>(a, 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.
   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
import "slices"
func binarySearch(a []T, x T) int {
	if i, ok := slices.BinarySearch(a, x); ok {
		return i
	} else {
		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
}
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 "sort"
func binarySearch(a []int, x int) int {
	i := sort.SearchInts(a, x)
	if i < len(a) && a[i] == x {
		return i
	}
	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
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;
}
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, 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;
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;
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);