Binary Search on Two-Dimensional Data

Title:: Binary Search on Two-Dimensional Data
Document type:: Technical Report
Author(s):: Riko Jacob
Abstract:: We consider the problem of searching for the predecessor (largest element that is smaller than some key) among elements that are organized as a matrix such that every row and every column is weakly monotonic (sorted matrix). \\ The results are matching upper and lower bounds for the number of accesses to the matrix and comparisons with the key.
Keywords:: sorted matrix; binary search
Year:: 2008
Year / month:: 2008-06-01 00:00:00
Pages:: 11
BibTeX

Occurrences: