ABSTRACT

Searching is one of the main computer applications in all other fields, including daily life. The basic problem consists of finding a given object in a set of objects of the same kind. Databases are perhaps the best examples where searching is the main task involved, and also where its performance is crucial. We use the dictionary problem as a generic example of searching for a key in a set of keys.

Formally, we are given a set S of n distinct keys∗ x1, . . . , xn, and we have to implement the following operations, for a given key x: