Logo

Programming-Idioms

History of Idiom 124 > diff from v25 to v26

Edit summary for version 26 by Foxy:
[Erlang] Added demo
↷

Version 25

2018-12-28, 10:40:46

Version 26

2018-12-28, 10:42:15

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.
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.
Demo URL
https://ideone.com/qlpwS4