Results 1 to 3 of 3

Math Help - find the k'th smallest in two arrays algorithm(psedo code)

  1. #1
    MHF Contributor
    Joined
    Nov 2008
    Posts
    1,401

    find the k'th smallest in two arrays algorithm(psedo code)

    i have two arrays ,each of size n, which are sorted.
    write an algorithm that finds the k'th smallest amongst the "sum" of the two arrays
    in O(lg min (k,2n-k))

    i have this idea of how to solve it.


    in the added picture
    i find the k smallest of array A by A[k] and k smallest of array B by B[k]

    and the k smallest of the sum is between those

    in my photo k2>k1

    i wrote the following function but i dont know how to know if i got the k'th smallest in the recurtion.and i am not sure abiut the sub arrays ranges in the recursive calls
    Mikum(A,q,r)
    k1=A[k/2]
    k2=B[k/2]
    If (x>y)
    Mikum(A,k, n)
    Mikum(B,0 ,k)
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,528
    Thanks
    773

    Re: find the k'th smallest in two arrays algorithm(psedo code)

    What is the "sum" of two arrays?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Joined
    Nov 2008
    Posts
    1,401

    Re: find the k'th smallest in two arrays algorithm(psedo code)

    sorry for the measleading term
    sum is sticking to two arrays together making then into one big 2n array

    for example
    A 1,2,3
    B 7,8,9
    then we need to find the k'th smallest in 7,8,9,1,2,3 or in 1,2,3,7,8,9
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. find the k'th smallest in array algorithm
    Posted in the Math Software Forum
    Replies: 1
    Last Post: December 12th 2011, 09:25 AM
  2. Replies: 3
    Last Post: January 8th 2010, 02:39 AM
  3. Find the smallest n possible to obtain...
    Posted in the Statistics Forum
    Replies: 3
    Last Post: November 11th 2009, 06:15 PM
  4. Find smallest n for which this is possible?
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: May 27th 2009, 10:40 AM
  5. Optimal algorithm for code cracking
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: February 26th 2009, 01:43 PM

Search Tags


/mathhelpforum @mathhelpforum