Erlang 2分探索 速報版

サンプル（速報版）

-module(binary_search).
-export([search/2]).
-include_lib("eunit/include/eunit.hrl").
-define(Middle,Mid = (Lo + Hi) div 2).
-ifdef(debug).
-define(print,io:format("~p:~p~n",[?MODULE,?LINE])).
-else.
-define(print,ok).
-endif.

% @spec search(Array,Target) -> {true,pos} | false
search(Array,Target) ->
        i_search(Array,Target,0,array:size(Array)-1).

i_search(Array,Target,Lo,Hi) when Lo =< Hi ->
    ?Middle,
    X = array:get(Mid,Array),
    if
           Target < X ->
                   ?print,
                   i_search(Array,Target,Lo,Mid -1);
           true ->
                  ?print,
                  i_search(Array,Target,Mid + 1, Hi)
   end;

i_search(Array,Target,Lo,Hi) when Lo > Hi ->
    Mid = (Lo + Hi ) div 2,
    X = array:get(Mid,Array),
    if
            Target =:= X ->
                    ?print,
                    {true,Hi};
            Hi =:= 0 ->
                    ?print,
                    false;
            true ->
                    ?print,
                    false
    end.

-ifdef(debug).
-define(FUNC(X,Y),search(X,Y)).
-define(AL(),array:from_list( [1,3,4,6,89] )).
s1_test() -> {true,0} = ?FUNC(?AL(),1).
s2_test() -> {true,1} = ?FUNC(?AL(),3).
s3_test() -> {true,2} = ?FUNC(?AL(),4).
s4_test() -> {true,3} = ?FUNC(?AL(),5).
s5_test() -> false = ?FUNC(?AL(),6).
-endif.

果たして、これでいいのか。



2012/1/21追記
s4_test()とs5_test()は故意に失敗するようなテストにしています。