Geek Answers Handbook

Binary search in Erlang in lg (n) time

I was looking for a possible job to do a binary search in Erlang, and I found http://ruslanspivak.com/2007/08/15/my-erlang-binary-search/ But I was wondering if the blog solution works in O (lg n). Now, since the repetition for binary search is: T (n) = T (n / 2) + c, which gives me the runtime of O (log n).

Since in array C you have the ability to access any element in O (1) time. But in erlang, if accessing the middle of the list takes cn time, then binary searching in linear total time is as bad as linear searching.

I came across lists: nth / 2 BIF to search for the nth item in a list, but I'm not sure about its runtime.

Any comments?

+5
source share
2 answers

There are several data structures that allow O (1) to be used in Erlang tables: ETS, tuples, and binaries.

Now none of them will be really suitable for binary search. The ETS table supports the search from the very beginning, and otherwise the data is copied to your process when the result is returned, which is unlikely to be optimal for your use.

Tuples allow O (1) access with help element/2, but changing them has certain overhead (which is why the array module uses tuple trees).

Then you have binaries ( <<1,2,3,4,5>>) that allow something similar to pointer arithmetic, as in the following example:

1> Sorted = <<$a,$b,$c,$d,$e,$f,$g,$h>>.
<<"abcdefgh">>
2> <<_:3/binary, X:1/binary, _/binary>> = Sorted.
<<"abcdefgh">>
3> X.
<<"d">>

, , , .

, , list_to_tuple/1 element/2.

; gb_tree O (log N) .

+6

nth - O (n). (, C - ).

-1
source

More articles:


All Articles