3.3 Sequential Search of Ordered Array

Let's jump back to the pile-of-things analogy from the beginning of this chapter (see Sequential Search). This time, suppose that instead of being in random order, the pile you're searching through is ordered on the property that you're examining; e.g., magazines sorted by publication date, if you're looking for, say, the July 1988 issue.

Think about how this would simplify searching through the pile. Now you can sometimes tell that the magazine you're looking for isn't in the pile before you get to the bottom, because it's not between the magazines that it otherwise would be. On the other hand, you still might have to go through the entire pile if the magazine you're looking for is newer than the newest magazine in the pile (or older than the oldest, depending on the ordering that you chose).

Back in the world of computers, we can apply the same idea to searching a sorted array:

18. <Sequentially search a sorted array of ints 18> =
/* 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 sorted in ascending order. */
int 
seq_sorted_search (int array[], int n, int key) 
{
  int i;

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

  return -1;
}

This code is included in 600.

At first it might be a little tricky to see exactly how seq_sorted_search() works, so we'll work through a few examples. Suppose that array[] has the four elements {3, 5, 6, 8}, so that n is 4. If key is 6, then the first time through the loop the if condition is 6 <= 3, or false, so the loop repeats with i == 1. The second time through the loop we again have a false condition, 6 <= 5, and the loop repeats again. The third time the if condition, 6 <= 6, is true, so control passes to the if statement's dependent return. This return verifies that 6 == 6 and returns i, or 2, as the function's value.

On the other hand, suppose key is 4, a value not in array[]. For the first iteration, when i is 0, the if condition, 4 <= 3, is false, but in the second iteration we have 4 <= 5, which is true. However, this time key == array[i] is 4 == 5, or false, so -1 is returned.

See also:  [Sedgewick 1998], program 12.4.