We call the structures used to organize data data structures . In our algorithm to find matches in a list, it was convenient to number the input values. Given a number, i , we can find the corresponding input value, a i . We call structures that contain values indexed by numbers arrays . A second useful structure is the record .
Records combine multiple values, such as names and phone numbers.
In your algorithms, some of you wondered how we'd keep the two together. Records are how computers do it. The Problem of Searching Today's question was intended to reveal a common problem that we often solve by computers, that of searching . The two variations of the question were to help you think about how the organization of data might affect the running time of the algorithm. We'll consider each case in turn, and also look at the running time in Big-O notation.