Erlang
binarysearch

ErlangのBinary Search

More than 3 years have passed since last update.
-module(binary_search).
-export([binary_search/2]).

%% > c(binary_search).
%% 5> binary_search:binary_search([], -1).
%% -1
%% 6> binary_search:binary_search([], 0).
%% -1
%% 7> binary_search:binary_search(lists:seq(3,100000),6 ).
%% 4
%% 8> binary_search:binary_search(lists:seq(3,100000),3 ).
%% 1

%% ソートされているリストの中にNを探す
binary_search(List, N) ->
  binary_search(List, N, 1, length(List), List).

%% _Listは今から処理するリスト
%% _OriListは変わらない、ずっと最初と同じリスト
%% 見つからなかったら、-1を返す

binary_search(_List, _N, Left, Right, _OriList ) when Left > Right ->
    -1; 
binary_search(_List, N, Left, Right, OriList ) when Left =< Right ->

  Middle = (Left + Right) div 2, 

  %% OriListを使って、リストの要素を特定している
  Item = lists:nth(Middle, OriList),

  case Item of
    N -> Middle; %% 見つかったら、ここでIndexを返す
    _ -> 
    case Item > N of
        true  -> binary_search(lists:sublist(OriList, Middle -1), N, Left, Middle-1,  OriList); %% left
        false -> binary_search(lists:nthtail(Middle, OriList), N, Middle+1, Right , OriList)  %% right
      end
  end.