# Compute median in unsorted array in $\mathcal{O}(\log{}n)$ space and $\mathcal{O}(\log{}n)$ passes

I want to compute the median in an array of size $m$ which consists of distinct integers from $\{0, 1, ..., n-1\}$, I have $m<n$. By median I mean the middle element (rounding up/down if the array size is even) in the sorted version of the array.

Ideally, the expected number of passes over the array should be $\mathcal{O}(\log{}n)$, the used memory should be $\mathcal{O}(\log{}n)$ bits and the solution should be exact. I'm flexible with the time complexity as long as it's feasible.

Since finding the median in an unsorted array is such a common problem I expected to quickly find some solution which suits my needs but after some research I'm wondering if this is even possible. Does anyone know a solution or where I could expect to find one?

The natural algorithm determines the $\log n$ bits of the median, MSB to LSB. Suppose that we have determined the $k$ MSBs of the median, $b_{m-1},\ldots,b_{m-k}$. Determine the number of integers in the array whose $k+1$ MSBs are $b_{m-1},\ldots,b_{m-k},1$, and use this to find the $(k+1)$th MSB of the median.
This algorithm uses $O(\log n)$ passes and $O(\log m + \log n) = O(\log n)$ space.
• How would you "use this to find the $(k+1)$th MSB of the median."? Commented Oct 13, 2017 at 14:35