Searching Semisorted Tables
Helmut Alt, Kurt Mehlhorn · SIAM Journal on Computing · 1985
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.