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
Re: find the k'th smallest in array algorithm
Does the black box works in constant time? Is 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 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.