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 ofints 16> = /* Returns the smallestisuch thatarray[i] ==key,

or -1 ifkeyis not inarray[].array[] must be an array ofnints. */intseq_search(intarray[],intn,intkey)

{inti;for(i= 0;i<n;i++)if(array[i] ==key)returni;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]