Optimal algorithms for generalized searching in sorted matrices

Hong Shen

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)


We present a set of optimal arid asymptotically optimal sequential and parallel algorithms for the problem of searching on an m x n sorted matrix in the general case when m≤n. Our two sequential algorithms have a time complexity of O(m log(2n/m)) which is shown to be optimal. Our parallel algorithm runs in O(log(log m/log log m) log(2n/m1-z)) time using m/log(log m/log log m) processors on a COMMON CRCW PRAM, where 0≤z < 1 is a monotonically decreasing function on m, which is asymptotically work-optimal. The two sequential algorithms differ mainly in the ways of matrix partitioning: one uses row-searching and the other applies diagonal-searching. The parallel algorithm is based on some non-trivial matrix partitioning and processor allocation schemes. All the proposed algorithms can be easily generalized for searching on a set of sorted matrices.

Original languageEnglish
Pages (from-to)221-230
Number of pages10
JournalTheoretical Computer Science
Issue number1-2
Publication statusPublished - 30 Nov 1997
Externally publishedYes


  • Matrix search problem
  • Optimal algorithm
  • Processors
  • Sorted matrix
  • Time complexity
  • Work-optimal


Dive into the research topics of 'Optimal algorithms for generalized searching in sorted matrices'. Together they form a unique fingerprint.

Cite this