Saturday, October 29, 2011

Online Median Tracing Algorithm

Given a stream of integers (flow read from disk or some other resource, like a sensor counting some events). How can we find the median of elements read so far?

It is an interesting online algorithm. Online, we mean the algorithm that can output result after any instance of input processing. For example, after reading i-elements we should be able to tell the median of i-elements read till now.

I read the question on Gulli blog, and came up with some solution. I have posted the algorithm on Geeksforgeeks.

Again, it is just for my reference of link. Any comments, please post on Geeksforgeeks.