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.
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;
}
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.
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;
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;