The problem of searching involves the problem of examining a collection of N records of data, each of which is identified by a key, and finding a data record that matches a pre-specified key. For example, if the collection of elements is a phone book, each data record consists of a name and a phone number, with the name being the key. Looking up the phone number of Jane Doe then constitutes an instance of a search problem.

A variety of data structures and search techniques are used to solve the search problem, each suited to a particular scenario. When the data records are stored in a linear fashion, one may use either an array or a linked list as the data structure used to hold the records. The advantage of an array is its random access property, namely that any element of the array...