Programming-Idioms

New implementation

Be concise.

Be useful.

All contributions dictatorially edited by webmasters to match personal tastes.

Please do not paste any copyright violating resource.

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

Other implementations
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;
}
def binarySearch(ar, el)
  res = ar.bsearch{|x| x == el}
  res ? res : -1
end
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.
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
}
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(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;
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;
    }
}
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);