# How to find the kth minimum element in an array

I am looking for an efficient algorithm to find the k'th minimum element in an unsorted array of n elements, where `1 <= k <= n`. The obvious thing is to sort the array first, then pick the k'th element, which will result in a running time of `O(n * log(n))` But I guess it can be done in a more efficient way, since sorting the array seems to do "too much". For example, for k=1 the task is to find the minimum of the array, which can be done in `O(n)`.

Does anyone know a better algorithm for k>=2?

• I don't know the answer offhand, but I know if you hit the CS (Computer Science) books for just a short time you'll run into the answer. For sure it's in Introduction to Algorithms, which is pretty definitive. :) But you should at least try to pick up some basic CS knowledge online so you can actually provide "what you've tried already" info like @gnat points out. – Wildcard Dec 24 '15 at 9:52
• I guess this Wikipedia article is what you are looking for: en.wikipedia.org/wiki/Selection_algorithm – Doc Brown Dec 25 '15 at 11:31
• – NoChance Dec 26 '15 at 2:00