, Homework Help - computer Science, Homework Help - computer Science, Maths
Chicago , U.S.A
Computer Science HelpComputer Science HelpComputer Science HelpComputer Science HelpComputer Science HelpComputer Science HelpComputer Science Help, Homework Help - computer Science

Question Details

How to find k-th largest in two sorted arrays ?
Answer Question



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 k-1 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 k-i-1 elements less than it in B[]. That is, B[k-i-1] should be < A[i] and B[k-i]>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.

Computer Science HelpHomeComputer Science HelpServiceComputer Science HelpSubjectsComputer Science HelpQ&A BoardComputer Science HelpAskQuestionComputer Science HelpSiteMap