Introduction

Lookup is nothing but checking whether an element is present in a container or finding the corresponding value for a key in the container. In the student database system and the hospital management system examples that we mentioned in the previous chapters, a common operation is to fetch a particular record from the vast amount of data stored in the system. A similar problem also presents itself while getting the meaning of a word from a dictionary, checking whether a person is allowed to enter a certain facility based on a set of records (access control), and many more applications.

For most of these scenarios, just going through all the elements linearly and matching the values would be extremely time-consuming, especially considering the vast amount of records that are stored. Let's take a simple example of looking up a word in a dictionary. There are roughly 170,000 words in the English dictionary. One of the simplest ways to do this is to traverse the dictionary linearly...