Ruslan’s Blog

I was lurking and watching Erlang quite some time during this year and finally decided give it a shot after Programming Erlang was released. I ordered book in pdf format to rest assured i’ll get it in fastest possible way. After i read book a bit i was hooked

Today i came across binary search in Erlang blog post and decided to implement quickly binary search myself. My first attempt was to do it in python as it’s my daily job’s programming language and it turned this way (no check for edge cases like empty sequence):

def binsearch(seq, key, start, end):
    if end < start:
        return -1
    mid = (start + end) / 2
    if key == seq[mid]:
        return mid
    if key < seq[mid]:
        return binsearch(seq, key, start, mid-1)
    if key > seq[mid]:
        return binsearch(seq, key, start+1, end)

After i looked at code a bit i was surprised i wrote it recursively, earlier i would do it like:

def binsearch(seq, key):
    start = 0
    end = len(seq) - 1

    while True:
        if end < start:
            return -1
        mid = (start + end) / 2
        if key == seq[mid]:
            return mid
        if key < seq[mid]:
            end = mid - 1
        else:
            start = mid + 1

Erlang obviously bends my mind :)

And my version in Erlang which was just exercise for myself and mainly looks like in original blog post:

-module(search).
-export([binsearch/2]).
-import(lists, [nth/2]).
-include_lib("eunit/include/eunit.hrl").

binsearch(List, Key) ->
    binsearch(List, Key, 1, length(List)).

binsearch(List, Key, LowerBound, UpperBound) ->
    if
        UpperBound < LowerBound -> -1;
        true ->
            Mid = (LowerBound + UpperBound) div 2,
            Item = nth(Mid, List),
            if
                Key < Item ->
                    binsearch(List, Key, LowerBound, Mid-1);
                Key > Item ->
                    binsearch(List, Key, Mid+1, UpperBound);
                true ->
                    Mid
            end
    end.

setup_test_() ->
    {setup,
     fun() -> [7, 11, 14, 40, 50] end,
     fun(L) ->
             [?_assertMatch(3, binsearch(L, 14)),
              ?_assertMatch(-1, binsearch(L, 70))]
     end
    }.

Running unit tests:

(em@localhost)1> search:test().
  All 2 tests successful.
ok