Q. Find the

===================================

Although there are numerous resources on the web that claim to solve it in log(n) or log(k) . But I have not found a complete solution which takes care of all cases, such as k < n or k < m or k > 2*n etc.,

i mean none took care of all cases.

So, I tried to get log(n+m) complexity, but i could not achieve it taking all kind of cases into considerations, every time i miss some of the case.

===================================

A help is needed here to get a full solution.

**kth**element from the union of two sorted arrays.(one of size**n**, other of size**m**).===================================

Although there are numerous resources on the web that claim to solve it in log(n) or log(k) . But I have not found a complete solution which takes care of all cases, such as k < n or k < m or k > 2*n etc.,

i mean none took care of all cases.

So, I tried to get log(n+m) complexity, but i could not achieve it taking all kind of cases into considerations, every time i miss some of the case.

===================================

A help is needed here to get a full solution.

Given an integer n and two sorted arrays A and B of length n, find the nth element in the union of the two arrays.

This problem can be solved easily using binary search.

Let:

A = {a1, a2, ..., a(n/2), a(n/2+1), ... a(n-1), an}

B = {b1, b2, ..., b(n/2), b(n/2+1), ... b(n-1), bn}

C = A union B.

bool cmp1 (int iA, int iB)

{

return A[iA] <= B[iB];

}

if cmp1(n/2, n/2) then we have that a(n/2) <= b(n/2).

Now, observe that any number in A[1...n/2] will be fixed in the first (n - 1) numbers of C, because there are n + 1 numbers that are greater or equal to they. These numbers are:

a(n/2+1), ... a(n), b(n/2), ..., b(n).

In other hand, not number in B[n/2+1, ..., n] will necessarily be in the first n numbers of C, because there are n numbers that are smaller or equal to they. These numbers are:

a1, ..., a(n/2), b1, ..., b(n/2).

Now, the nth number in C will be the (n/2)th number in (A[n/2+1...n] union B[1...n/2]).

The case when !cmp1(n/2, n/2) is analogous.

Now let see how transform your problem to this one.

Let A and B your input arrays (size(A) = n and size(B) = m)

if n < k we can fill A with values equal to infinity and now n = k. (filling process)

if m < k we can fill B with values equal to infinity and now m = k.

Let C = (A union B).

Not number in A[k+1...n] will be the kth number in C because there are k numbers that are smaller or equal to they.

These numbers are A[1...k].

Not number in B[k+1...n] will be the kth number in C because there are k numbers that are smaller or equal to they.

These numbers are B[1...k].

Now your problem is reduced to find the kth element in two arrays of size k (A[1...k], B[1...k]), that is exactly the above problem. The complexity is O(logk)

NOTE: The filling process is abstract. We can simulate it replacing cmp1 by cmp2:

bool cmp2 (int iA, int iB)

{

if (iB >= m)

return true;

if (iA >= n)

return false;

return A[iA] <= B[iB];

}

There is other solution with complexity O (min (k, m, n)), but it's difficult for me explain it in english.

Thanks.

That part about filling it with inf. upto k, was brilliant.

(how could I miss it. so obvious, thanks again.)