  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)$.
