Should Tables Be Sorted?

Abstract

Optmaahty questions are examined m the following information retrieval problem. Given a set S of n keys, store them so that queries of the form, "Is x E S?" can be answered quickly It is shown that m a rather general model including all the commonly used schemes, [lg(n + I)] probes to the table are needed m the worst case, prowded the key space is sufficiently large The effects of smaller key space and arbitrary encoding are also explored