> 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