#1
  1. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Apr 2004
    Posts
    2
    Rep Power
    0

    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 (http://forums.devshed.com/t67403/s.html). 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.
  2. #2
  3. No Profile Picture
    Contributing User
    Devshed Intermediate (1500 - 1999 posts)

    Join Date
    Feb 2004
    Location
    London, England
    Posts
    1,585
    Rep Power
    1373
    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
  4. #3
  5. No Profile Picture
    Contributing User
    Devshed Intermediate (1500 - 1999 posts)

    Join Date
    Feb 2004
    Location
    San Francisco Bay
    Posts
    1,939
    Rep Power
    1313
    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.
  6. #4
  7. No Profile Picture
    Contributing User
    Devshed Intermediate (1500 - 1999 posts)

    Join Date
    Feb 2004
    Location
    London, England
    Posts
    1,585
    Rep Power
    1373
    Originally Posted by Lux Perpetua
    No, DevCoach. Log time is enough. In fact, this problem is amenable to something very similar to binary search.
    <algorithm snipped>
    Yes, you are right. Very neat.

    Dave - The Developers' Coach
  8. #5
  9. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Apr 2004
    Posts
    2
    Rep Power
    0
    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.
  10. #6
  11. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Nov 2010
    Posts
    1
    Rep Power
    0
    Originally Posted by spikecuz
    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.
    i am working on this algorithm friend but i didn't got the question very clear >> so could you please explain if we gonna merge the two lists and how

IMN logo majestic logo threadwatch logo seochat tools logo