# Find ANY ONE of the k smallest elements

Hey guys, I was hoping someone could help me out with this problem, I might be over thinking it too much and the answer might be very simple but its not getting to me.

The problem has to deal with the k-smallest element problem, you are given n elements and an integer k such that 1 < k < n. The problem is to find ANY ONE of the k smallest elements.

So for example, if k = 4, the output may be either the first, second, third, or fourth-smallest element.

I am looking for a FAST algorithm to solve this problem and to figure out how many comparisons it performs. I also need to give a lower bound as a function of n and k on the number of comparisons needed to solve this problem.

Any help is appreciated, thanks!

Joey

• oh wow nevermind the answer is so simple =/

I don't even need to think about k-select algorithms here!
• I will give an answer just for the sake of it.
This is a classic problem at job interviews

One obvious answer is to sort all n elements in a list using some efficient sort algorithm, e.g. quicksort, which gives a worst-case scenario of O(n^2).

However, a better solution is to use a min-heap instead of a list. A min-heap obtains a worst-case scenario of O(n + k*log k).