Edited at

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.