> Right out the gate: the numbers must be sorted. I was somewhat pained by this, as this is an interview question I've gotten, and I clearly annoyed the interv

> Right out the gate: the numbers must be sorted. I was somewhat pained by this, as this is an interview question I've gotten, and I clearly annoyed the interviewer by knowing this isn't true, and you can avoid a full sort (which, at least two others have noted). https://en.wikipedia.org/wiki/Quickselect https://en.wikipedia.org/wiki/Quickselect