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:

19. <Sequentially search a sorted array ofints 19> = /* Returns the smallestisuch thatarray[i] ==key,

or -1 ifkeyis not inarray[].array[] must be an array ofnints sorted in ascending order. */intseq_sorted_search(intarray[],intn,intkey)

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

This code is included in 602.

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.