| Range Medians (2008) | |||||||||
Abstract | |||||||||
| We study a generalization of the classical median finding problem to batched query case: given an array of unsorted $n$ items and $k$ (not necessarily disjoint) intervals in the array, the goal is to determine the median in {\em each} of the intervals in the array. We give an algorithm that uses $O(n\log n + k\log k \log n)$ comparisons and show a lower bound of $\Omega(n\log k)$ comparisons for this problem. This is optimal for $k=O(n/\log n)$.. Comment: To appear in ESA 08 | |||||||||
Details der Publikation | |||||||||
| |||||||||