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

Question

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?

Answer 1

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.

Answer 2

As @Yuval Filmus pointed out, you can use a histogram approach.

Since you know the number of integers and that they are all distinct you immediately know the rank. Now you create 2 histograms/buckets, one for all integers whose MSB is 0 the other one for 1's. By the number of elements in the buckets you can conclude in which one the median must be. You have effectively found the MSB of the median, simply repeat this procedure for the rest of the bits.

A Java implementation which does this can be found here.