Towards Optimal Range Medians

Details Towards Optimal Range Medians Towards Optimal Range Medians

2009-01-13

arxiv.org/abs/0901.1761v1

Computer Science

Data Structures and Algorithms

Scientific paper

We consider the following problem: given an unsorted array of $n$ elements, and a sequence of intervals in the array, compute the median in each of the subarrays defined by the intervals. We describe a simple algorithm which uses O(n) space and needs $O(n\log k + k\log n)$ time to answer the first $k$ queries. This improves previous algorithms by a logarithmic factor and matches a lower bound for $k=O(n)$. Since the algorithm decomposes the range of element values rather than the array, it has natural generalizations to higher dimensional problems -- it reduces a range median query to a logarithmic number of range counting queries.

Affiliated with

Also associated with

No associations

Rating

Towards Optimal Range Medians does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Towards Optimal Range Medians, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Towards Optimal Range Medians will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-71905