Answer Algorithm Find_kth_largest { Input : Given A,B sorted array. Output : Kth largest. Idea = We will find te median of the median 2K elements , k elements from A and k elements from B. 1. The kth largest among the union of A[] and B[] would be in the first k elements of of A[] and b[] 2. Get first K elements of A and B. 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.
5. Output the median of 2 or 3. }
The idea of finding the median of 2k elements is great but the problem is that both the arrays need not have k elements in them. This is where the algorithm fails. A solution to that could be to use binary search in each array to check if an element is the kth element. Checking if an element is the kth takes O(k) time since the kth element should have exactly k1 elements less than it. It is easy to see that the number of elements less than A[i] in A[] is i. If it is the kth element in the combined array, it should have ki1 elements less than it in B[]. That is, B[ki1] should be < A[i] and B[ki]>A[i]. This way, the solution requires a binary search on A[] and a binary search on B[]. Therefore it takes O(log(m) + log(n)) time, where m and n are the sizes of the 2 arrays.
