finding smallest k elements in array in O(k) This is an interesting question I have found on the web. Given an array containing n numbers (with no information about them), we should pre-process the array in linear time so that we can return the k smallest elements in O(k) time, when we are given a number 1 &lt;= k &lt;= n

I have been discussing this problem with some friends but no one could find a solution; any help would be appreciated!

quick notes:
-the order of the k smallest elements is not important
-the elements in the array are number , might be integers and might be not (so no radix sort)
-the number k is not know in the pre-processing stage.the preprocessing is O(n) time. the function ( find k smallest elements) on O(k) time .
Preprocess the array of $n$ values in time $O(n)$:


$i\leftarrow n$
while $i&gt;2$

Compute the median $m$ of $A[1..i]$ in time $O(i)$
partition $A[1..i]$ into $A[1..i/2-1] \leq m$ and $A[i/2+1..i]\geq m$ in the same time.
$i \leftarrow \lfloor i/2 \rfloor$



The total precomputation time is within $O(1+2+4+...+n)\subseteq O(n)$

Answer a query for the $k$ smallest elements in $A$ in time $O(k)$:


$l\leftarrow \lfloor \log_2 k \rfloor$
select the $(k-2^l)$th element $x$ of $A[2^l..2^{l+1}]$ in time $O(2^l)\subseteq O(k)$
partition $A[2^l..2^{l+1}]$ by $x$ in the same time


$A[1..k]$ contains the $k$ smallest elements.

References:


In 1999, Dor and Zwick gave an algorithm to compute the median of $n$ elements in time within $2.942 n + o(n)$ comparisons, which yields an algorithm to select the $k$th element from $n$ unordered elements in less than $6n$ comparisons.