Towards Optimal Range Medians
| dc.creator | Gfeller, Beat | |
| dc.creator | Sanders, Peter | |
| dc.date | 2009-01-13 | |
| dc.date.accessioned | 2026-07-07T12:28:56Z | |
| dc.date.available | 2026-07-07T12:28:56Z | |
| dc.description | 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. | |
| dc.identifier | https://arxiv.org/abs/0901.1761 | |
| dc.identifier | http://arxiv.org/abs/0901.1761 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/215711 | |
| dc.subject | Data Structures and Algorithms | |
| dc.title | Towards Optimal Range Medians | |
| dc.type | text |