Searching Semisorted Tables

Helmut Alt, Kurt Mehlhorn

Abstract

A “semisorted table” is a one-dimensional array containing n data, which are not necessarily sorted, but can appear in p different permutations of the ascending order. We consider the problem of searching in such a table without knowing, in which one of the p permutations the data are stored (SST). It is shown that any deterministic search algorithm for SST needs at least $\sqrt[n]{p}$ comparisons in the worst case. This lower bound is generalized to average case performance even for nondeterministic algorithms. Some examples are given where the lower bound is tight.
BibTeX
@article{alt1985searching,
  author = {Helmut Alt and Kurt Mehlhorn},
  title = {{Searching Semisorted Tables}},
  journal = {SIAM Journal on Computing},
  year = {1985},
  doi = {10.1137/0214059},
}

Loading related content...

Figure