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

1. ## 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?

2. ## 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.