Logo

Programming-Idioms

History of Idiom 124 > diff from v24 to v25

Edit summary for version 25 by Foxy:
New Erlang implementation by user [Foxy]
↷

Version 24

2018-08-03, 20:48:06

Version 25

2018-12-28, 10:40:46

Idiom #124 Binary search for a value in sorted array

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

Idiom #124 Binary search for a value in sorted array

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

Extra Keywords
dichotomic dichotomy
Extra Keywords
dichotomic dichotomy
Code 
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.