Skip to content

Instantly share code, notes, and snippets.

@thiagomoretto
Created December 8, 2010 06:14
Show Gist options
  • Save thiagomoretto/732966 to your computer and use it in GitHub Desktop.
Save thiagomoretto/732966 to your computer and use it in GitHub Desktop.
Binary chop in Erlang
-module(chop).
-export([chop/2]).
chop(_Value, []) ->
-1;
chop(Value, List) ->
case (length(List) + 1) div 2 of
0 ->
-1;
Middle ->
Current = lists:nth(Middle, List),
chop(Value, List, Current, 0, length(List), Middle - 1)
end.
chop(_Value, [], _Current, _Low, _Hi, _Middle) ->
-1;
chop(_Value, _List, _Current, Low, Hi, _Middle) when Hi < Low ->
-1;
chop(Value, _List, Current, Low, Hi, _Middle) when Value /= Current, Hi == Low ->
-1;
chop(Value, List, Current, Low, Hi, _Middle) when Value < Current, Hi > Low ->
MidIndex = (Low + Hi) div 2,
chop(Value, List, lists:nth(MidIndex + 1, List), Low, MidIndex, MidIndex);
chop(Value, List, Current, Low, Hi, _Middle) when Value > Current, Hi > Low ->
MidIndex = (Low + Hi) div 2,
chop(Value, List, lists:nth(MidIndex + 1, List), MidIndex + 1, Hi, MidIndex);
chop(Value, _List, Current, _Low, _Hi, Middle) when Value == Current ->
Middle.
-module(chop_test).
-include_lib("eunit/include/eunit.hrl").
chop_test_() ->
[?_assertEqual(-1, chop:chop(3, [])),
?_assertEqual(-1, chop:chop(3, [ 1 ])),
?_assertEqual(0, chop:chop(1, [ 1 ])),
?_assertEqual(0, chop:chop(1, [ 1, 3, 5 ])),
?_assertEqual(1, chop:chop(3, [ 1, 3, 5 ])),
?_assertEqual(2, chop:chop(5, [ 1, 3, 5 ])),
?_assertEqual(-1, chop:chop(0, [1, 3, 5])),
?_assertEqual(-1, chop:chop(2, [1, 3, 5])),
?_assertEqual(-1, chop:chop(4, [1, 3, 5])),
?_assertEqual(-1, chop:chop(6, [1, 3, 5])),
?_assertEqual(0, chop:chop(1, [1, 3, 5, 7])),
?_assertEqual(1, chop:chop(3, [1, 3, 5, 7])),
?_assertEqual(2, chop:chop(5, [1, 3, 5, 7])),
?_assertEqual(3, chop:chop(7, [1, 3, 5, 7])),
?_assertEqual(-1, chop:chop(0, [1, 3, 5, 7])),
?_assertEqual(-1, chop:chop(2, [1, 3, 5, 7])),
?_assertEqual(-1, chop:chop(4, [1, 3, 5, 7])),
?_assertEqual(-1, chop:chop(6, [1, 3, 5, 7])),
?_assertEqual(-1, chop:chop(8, [1, 3, 5, 7]))
].
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment