3.1 Sequential Search

Suppose that you have a bunch of things (books, magazines, CDs, ...) in a pile, and you're looking for one of them. You'd probably start by looking at the item at the top of the pile to check whether it was the one you were looking for. If it wasn't, you'd check the next item down the pile, and so on, until you either found the one you wanted or ran out of items.

In computer science terminology, this is a sequential search (see sequential search). It is easy to implement sequential search for an array or a linked list. If, for the moment, we limit ourselves to items of type int, we can write a function to sequentially search an array like this:

16. <Sequentially search an array of ints 16> =
/* Returns the smallest i such that array[i] == key, 
   or -1 if key is not in array[]. 
   array[] must be an array of n ints. */
int 
seq_search (int array[], int n, int key) 
{
  int i;

  for (i = 0; i < n; i++)
    if (array[i] == key)
      return i;
  return -1;
}

This code is included in 595 and 600.

We can hardly hope to improve on the data requirements, space, or complexity of simple sequential search, as they're about as good as we can want. But the speed of sequential search leaves something to be desired. The next section describes a simple modification of the sequential search algorithm that can sometimes lead to big improvements in performance.

See also:  [Knuth 1998b], algorithm 6.1S; [Kernighan 1976], section 8.2; [Cormen 1990], section 11.2; [Bentley 2000], sections 9.2 and 13.2, appendix 1.

Exercises:

1. Write a simple test framework for seq_search(). It should read sample data from stdin and collect them into an array, then search for each item in the array in turn and compare the results to those expected, reporting any discrepancies on stdout and exiting with an appropriate return value. You need not allow for the possibility of duplicate input values and may limit the maximum number of input values. [answer]