find_Nth_from_two_sorted_list.erl

-module(find_Nth_from_two_sorted_list).

-compile(export_all).

find([], B, N) ->
    lists:nth(N, B);
find(A, [], N) ->
    lists:nth(N, A);
find([H1 | _], [H2 | _], 1) ->
    max(H1, H2);
find(A, B, N) ->
    NeedToKill = lists:min([length(A), length(B), N div 2]),
    case lists:nth(NeedToKill, A) > lists:nth(NeedToKill, B) of
        true ->
            find(lists:nthtail(NeedToKill, A), B, N - NeedToKill);
        _ ->
            find(A, lists:nthtail(NeedToKill, B), N - NeedToKill)
    end.

test(LL, N) ->
    A = lists:reverse(lists:sort([rand:uniform(100000) || _ <- lists:seq(1, LL)])),
    B = lists:reverse(lists:sort([rand:uniform(100000) || _ <- lists:seq(1, LL)])),
    Res = find(A, B, N),
    Res = lists:nth(N, lists:reverse(lists:sort(A ++ B))).
    
% 1> [test:test(50, 40)  || _ <- lists:seq(1, 10000)].