Finding kth largest element in a union of two arrays.

Given two *sorted* arrays of n elements each, is it possible to find the kth smallest element in the union of the arrays in a logarthimic time algorithm? I noticed a similar posting with a single unsorted array (URL). I do realise that I need to do some sort of binary search, but Im not exactly sure how to begin since I have two arrays and not one.

Anyone had any experience with a similar problem? Thanks.

If you had a single sorted array A then the kth smallest element would be A[k], a constant time operation. To find the kth smallest element of two sorted arrays you would need to merge the first k elements of the arrays. This can be done in O(k), but not logarithmic time.

Dave - The Developers' Coach

No, DevCoach. Log time is enough. In fact, this problem is amenable to something very similar to binary search. Suppose my arrays are A and B. The idea is to keep track of two indices, a (for A) and b (for B), such that a + b = k - 1 (it's very important to maintain this invariant). It's easy to check whether A[a] or B[b] is the answer: A[a] is the answer if and only if

B[b-1] <= A[a] <= B[b],

and B[b] is the answer if and only if

A[a-1] <= B[b] <= A[a],

where we use the convention that A[-1] = B[-1] = "negative infinity." (This can be determined in constant time.) Moreover, if neither of these is the case, you can divide the problem in half: if A[a] < B[b-1], you restrict your attention to the portion of A above index a and the portion of B below index b, and otherwise (it must be the case that B[b] < A[a-1]), you restrict your attention to the portion of A below index a and the portion of B above index b. (If you start with a and b in the middle of the arrays and always make the new indices be in the middle of the subarrays you're considering at that point, this step will always divide the problem in half.)

I haven't tested that algorithm (I just came up with it), so I can't guarantee that it works, but I guarantee that it will work with at most very slight modifications.

Yes, you are right. Very neat.

Dave - The Developers' Coach

Lux Perpetua, I'm sorry for the late reply. I only had time to implement the algorithm now. I just wanted to thank you very much for your help. It worked perfectly. I guess the invariant was the point I overlooked.