We study a generalization of the classical median finding problem
to batched query case: given an array of unsorted n items
and k intervals in the array, the goal is to determine
the median in each of the intervals in the array. We give
an algorithm that uses O(n log k) comparisons and show
a matching lower bound of Vmega(n log k) comparisons for
this problem.

PDF /
PSSlides
[source].
Last modified: Tue May 27 22:54:19 CDT 2008