Results 1 to 2 of 2

Math Help - find the k'th smallest in array algorithm

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

    find the k'th smallest in array algorithm

    there is a black box which calculates the floor(in/m) smallest number in the array
    use the black box to calculate the "k" smallest number in the array in lenear time

    (n is the size of the array ,m is a constant)

    need guidance on the general idea of solving it

    ?

    if i=m/2 then we get the median

    what now?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,561
    Thanks
    785

    Re: find the k'th smallest in array algorithm

    Does the black box works in constant time? Is m given? What other operations can you do, e.g., can you exchange two array elements? Can you run the black box on a part of the array? If yes, then is n going to be the length of the part or of the whole array?

    My idea is to set i = m, find the largest element and exchange it with the last element of the array. Then repeat the process with the first n - 1, n - 2, etc. elements.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 2
    Last Post: December 14th 2011, 07:30 AM
  2. Algorithm - Finding index of an array
    Posted in the Math Topics Forum
    Replies: 5
    Last Post: March 5th 2011, 10:56 AM
  3. Replies: 2
    Last Post: May 16th 2010, 11:18 AM
  4. Find the smallest n possible to obtain...
    Posted in the Statistics Forum
    Replies: 3
    Last Post: November 11th 2009, 07:15 PM
  5. Find smallest n for which this is possible?
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: May 27th 2009, 11:40 AM

Search Tags


/mathhelpforum @mathhelpforum