|
|
|
|
|
|
|
To see how the While loop and the subsequent assignment statement work, let's look at the two possibilities: either item is in the list or it is not. If item is in the list, the loop terminates when the expression index < length is TRUE and the expression item != list[index] is FALSE. After loop exit, the variable found is therefore assigned the value of the expression index < length, which is TRUE. On the other hand, if item is not in the list, the loop terminates when the expression index < length is FALSE-That is, when index becomes equal to length. Subsequently, the value assigned to found is FALSE (see Figure 12-1). |
|
|
|
|
|
|
|
|
We can use this sequential search function in any program requiring a list search. In the form shown, it searches a list of ItemType components, provided that ItemType is an integral type. When the function is used with a list of floating point values, it must be modified so that the While statement tests for near equality (for the reasons discussed in Chapter 10). In the following statement, it is assumed that EPSILON is defined as a global constant. |
|
|
|
|
|
|
|
|
while (index < length && fabs(item - list[index]) >= EPSILON)
index++; |
|
|
|
|
|
|
|
|
The sequential search algorithm finds the first occurrence of the searched-for item. How would we modify it to find the last occurrence? We would initialize index to length-1 and decrement index each time through the loop, stopping when we found the item we wanted or when index became-1. |
|
|
|
|
|
|
|
|
Before we leave this search algorithm, let's introduce a variation that makes the program more efficient, although a little more complex. The |
|
|
|
|
|
|
|
|
Figure 12-1
Generalized Sequential Search |
|
|
|
|
|
