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