Recent Erlang releases (since R12B) have array module included.

Now binary search algorithm can be implemented quite efficiently with functional arrays:

-module(bsa). -export([binsearch/2]). binsearch(Arr, Key) -> binsearch(Arr, Key, 0, array:size(Arr)). binsearch(Arr, Key, LowerBound, UpperBound) -> Mid = (LowerBound + UpperBound) div 2, Item = array:get(Mid, Arr), if UpperBound < LowerBound -> -1; Key < Item -> binsearch(Arr, Key, LowerBound, Mid-1); Key > Item -> binsearch(Arr, Key, Mid+1, UpperBound); true -> Mid end.

Running time for *lists based* binary search (just for comparison):

56> {Time, Val} = timer:tc(search, binsearch, 56> [lists:seq(1, 1000000), 1000000]). {506513, 1000000}

Running time for *array based* binary search:

57> f(). ok 58> {Time, Val} = timer:tc(bsa, binsearch, 58> [array:from_list(lists:seq(1, 1000000)), 1000000]). {17, 999999}

{ 3 comments… read them below or add one }

Using binsearch for lists isn’t very clever (in fact it is stupid . For lists it is much better to just use linear search. Using binsearch of lists in erlang will lead to O(N^2) algorithm, instand of expected O(log N). Use linear search which is O(N), then compare.

Hi Witold,

I’m not encouraging to use binsearch for lists in Erlang, that was just my experiment

Actually I wrote about the fact that linear search is faster for lists in Erlang than binsearch:

http://ruslanspivak.com/2007/08/17/more-about-binary-search-in-erlang/

This topic is quite old. But you my find the random access lists a interesting topic. I implemented them in Erlang and have O(1) cons, head, tail operations, and log(n) for accessing any element. Yep!

http://github.com/baryluk/ral