The Median

In the Quicksort challenges, you sorted an entire array. Sometimes, you just need specific information about a list of numbers, and doing a full sort would be unnecessary. Can you figure out a way to use your partition code to find the median in an array?

Challenge
Given a list of numbers, can you find the median? The purpose of this challenge is to find the median without needing to sort all the elements.

Constraints
There may be will be less than 15,000 elements. There will an odd number of elements. There may be duplicate numbers.

Output
Output one integer, the median.

Running Time
Your code should run in O(n) time.