Home Bookmarks Papers Blog

Range medians

Sariel Har-Peled, and S. Muthukrishnan.


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 / PS
Slides [source].
Last modified: Tue May 27 22:54:19 CDT 2008