Find k-th largest in two sorted arrays

Find kth largest element in two sorted arrays.

Can there be a solution better that O(k)


Solution 1
=========

Suppose input array's are in the following fashion
A[] = {2, 3, 7, 12, 27, 81, 91}
b[] = {1, 25, 32, 74, 89}

1. Take two pointers ptr1 and ptr2 at start in A[] and B[]
2. if(A[i] > B[j])
j++;
else
i++;
3. if ( (i +j ) == k)
compare A[i] and B[j] and return the larger of them
else
repeat step2.

Time Complexity = O(k)

Solution2
==========

Idea = We have to find the median of first k elements of A and B and k = 5

1. The kth largest among the union of A[] and B[] would be in the first k elements of of A[] and b[]
2. Consider k elements from A[] and B[] which results in the following array
a[] = {2. 3, 7, 12, 27}
b[] = {1, 25, 32, 74, 89}
3. Compare (A[mid], B[mid])
if (A[mid] is GT)
{
For ArrayA = We can skip a[mid]..a[k] elements since a[mid] is greater and all elements from a[0]..a[mid] are valid candidates for being the median; since A[mid] is the greater element no point considering bigger elements than that for the median
For Array B = We can skip b[0]...b[mid] elements since b[mid] is less; so all elements less than are not valid candidates for being median.
}
4. Repeat Step3 till you are left with either 2 or 3 elements then you do a comparision and find kth largest.

Time Complexity = O(log k)

Example showing Solution 2
=========================

A[] = { 2, 3, 7, 12, 27}
B[] = {1, 25, 32, 75, 89}

After step2 i.e. k elements from both arrays
A[mid] = 7 and B[mid] = 32

B[mid] is Greater.

Now array becomes after step3
a[] = {7, 12, 27}
b[] = { 1, 25, 32}

a[mid] = 12 and b[mid] = 25
After step3 the arrays become
a[] = { 12, 27} -- skpping the left portion of smaller element array
b[] = { 1, 25} -- skipping the right portion of larger element array

Now a[mid] = 12 and b[mid] = 1
after step3 the array becomes
a[] = {12}
b[] = {1,25}

Find the median of 12, 1, 25 in O(1) which is 12 which is the 5th largest