Classic problem — Q: Given an unsorted int array, find its median in O(N) time. For simplicity, we can first assume array size is odd.

I think we can use any data structure. We can scan the array multiple times.

—-simple partition algo

Pick a random item in the array as pivot value and partition the array. Let’s say we are unlucky and get 12% low vs 88% high. So we discard the 12% and repeat. Suppose then we get 66% vs 22% (within high section). We would then discard the 22%.

So we are likely to require 2N “visits”, I don’t think it would degrade to ((N logN).

—-fancy idea — weighted pivot

In one scan find the max and min. Calculate the mid value. Say this is 23.5, not even an integer. I will use this as a pivot value to partition the array into 2 segments.

Suppose N=101, so I’m looking for #51 item. Suppose left segment has 10 and right segment has 91, so I discard left segment. Now I’m looking for the #41 in the remaining array.

Now I find max and min again (if necessary). Now, Instead of getting the mid point between them, I will use a weighted pivot of (10*min+91*max)/101, so this pivot is shifted to the right, based on suspicion of a right-heavy histogram.

–complexity?

On average, I should get N+N/2+N/4 … <2N

Worst case? The earlier illustration is rather unlucky since that histogram happens to be right-heavy. In such a case, my “weighted pivot” idea should alleviate it.