6.1 Searching

Searching is the process of selecting particular information from a collection of data based on specific criteria. You are familiar with this concept from your experience in performing web searches to locate pages containing certain words or phrases or when looking up a phone number in the telephone book. In this text, we restrict the term searching to refer to the process of finding a specific item in a collection of data items.

The search operation can be performed on many different data structures. The ordered sequence search, which is the focus in this chapter, involves finding an item within a sequence using a search key to identify the specific item. A key is a unique value used to identify the data elements of a collection. In collections containing simple types such as integers or floating-points, the values themselves are the keys. For collections of complex types, a specific data component has to be identified as the key. In some instances, a key may consist of multiple components, which is known as a compound key.