Algorithms (Dec 2021)

Searching Monotone Arrays: A Survey

  • Márcia R. Cappelle,
  • Les R. Foulds,
  • Humberto J. Longo

DOI
https://doi.org/10.3390/a15010010
Journal volume & issue
Vol. 15, no. 1
p. 10

Abstract

Read online

Given a monotone ordered multi-dimensional real array A and a real value k, an important question in computation is to establish if k is a member of A by sequentially searching A by comparing k with some of its entries. This search problem and its known results are surveyed, including the case when A has sizes not necessarily equal. Worst case search algorithms for various types of arrays of finite dimension and sizes are reported. Each algorithm has order strictly less than the product of the sizes of the array. Present challenges and open problems in the area are also presented.

Keywords