-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.
More than 5 years have passed since last update.
Register as a new user and use Qiita more conveniently
- You get articles that match your needs
- You can efficiently read back useful information
- You can use dark theme
List of users who liked
00