2026-07-072026-07-07http://salesiana.dossiersoluciones.com/handle/123456789/164008We 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 $Ω(n\log k)$ comparisons for this problem. This is optimal for $k=O(n/\log n)$.To appear in ESA 08Data Structures and AlgorithmsOther Computer Sciencetext