2008/07/01 by Sariel Har-Peled, S. Muthukrishnan, Har-Peled, Sariel +1
Computer Science · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Other Computer Science (cs.OH) #cs.DS #cs.OH
paper · pdf · doi:10.48550/arxiv.0807.0222
To appear in ESA 08
arxiv created 2008/07/01 · arxiv updated 2009/12/01
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(nlog n + klog k log n) comparisons and show a lower bound of Ω(nlog k) comparisons for this problem. This is optimal for k=O(n/log n).