Algorithms in a Nutshell

Sequential Search

Sequential Search, also called linear search, is the simplest of all searching algorithms. It is a brute-force approach to locating a single target value, t, in some collection, C. It finds t by starting at the first element of the collection and examining each subsequent element until either the matching element is found or each element of the collection has been examined.

Consider the case of a moderate-size restaurant with 10–20 tables that requires reservations for all customers. The restaurant is close to a large medical center, and many of its customers are medical staff of the center or family members of patients at the center. The restaurant advertises that they will locate any patron in case of emergency and deliver messages to that person promptly. When customers are seated at a designated table, the hostess records the names of the customers with that table and erases the names when the party leaves. To locate a patron in the restaurant at any given moment, the hostess simply scans through the information for the collection of tables.

Input/Output

There must be some way to obtain each element from the collection being searched; the order is not important. If a collection A supports indexing, then an index value i can be used to retrieve element A[i]. Often a collection C is accessible by using a read-only iterator that retrieves each element from C (as, for example, a database cursor in response to an SQL query). Accessing the elements by the iterator ...