Finding median in read-only memory on integer input

Timothy M. Chan, J. Ian Munro, Venkatesh Raman

Research output: Contribution to journalArticlepeer-review


Starting with Munro and Paterson (1980) [13], the selection or median-finding problem has been extensively studied in the read-only memory model and in streaming models. Munro and Paterson's deterministic algorithm and its subsequent refinements require at least polylogarithmic or logarithmic space, whereas the algorithms by Munro and Raman (1996) [14] and Raman and Ramnath (1999) [15] can be made to use just O(1) storage cells but take O(n1+ε) time for an arbitrarily small constant ε>0.In this paper, we initiate the first study on this problem when the input is a sequence of integers. We show that faster selection algorithms in read-only memory are possible if the input is a sequence of integers. For example, one of our algorithms uses O(1) storage cells and takes O(nlg U)1 time where U is the universe size. Another algorithm uses O(1) storage cells and takes O(nlg nlg lg U) time. A combination of the two yields an algorithm that uses O(1) words of space and takes O(nlg1+ε n) time, a bound independent of U. We also describe an O(n)-time algorithm for finding an approximate median using O(lgε U) storage cells.All our algorithms are simple and deterministic. Interestingly, one of our algorithms is inspired by 'centroids' of binary trees and finds an approximate median by repeatedly invoking a textbook algorithm for the 'majority' problem. This technique could be of independent interest.

Original languageEnglish (US)
Pages (from-to)51-56
Number of pages6
JournalTheoretical Computer Science
StatePublished - 2015
Externally publishedYes


  • Centroid of a tree
  • Integers
  • Majority finding
  • Read-only memory
  • Selection

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Finding median in read-only memory on integer input'. Together they form a unique fingerprint.

Cite this