|
|
|
|
|
|
|
the minimum value. Simply changing the relational operator in the inner loop from "<" to ">" effects this change. Of course, minIndex would no longer be a meaningful identifier and should be changed to maxIndex. |
|
|
|
|
|
|
|
|
Sequential Search in a Sorted List |
|
|
|
|
|
|
|
|
When we search for an item in an unordered list, we won't discover that the item is missing until we reach the end of the list. If the list is ordered, we know that an item is missing when we pass its correct place in the list. For example, if a list contains the values |
|
|
|
|
|
|
|
|
and we are looking for 12, we need only compare 12 with 7, 11, and 13 to know that 12 is not in the list. |
|
|
|
|
|
|
|
|
If the search item is greater than the current list component, we move on to the next component. If the item is equal to the current component, we have found what we are looking for. If the item is less than the current component, then we know that it is not in the list. In either of the last two cases, we stop looking. We can restate this algorithmically as follows. |
|
|
|
|
|
|
|
|
Set current position to beginning of list
WHILE item > current component in list AND more places to look
Increment current position
Set found = (item equals current component) |
|
|
|
|
|
|
|
|
We can make this algorithm more efficient by removing the compound condition ("AND more places to look"), as we did in Search2. We store item as a sentinel into list[length]. On exit from the loop, we can set found to TRUE if item is equal to the current component and the current position does not equal length. |
|
|
|
|
|
|
|
|
Store a copy of item beyond end of list
Set current position to beginning of list
WHILE item > current component in list
Increment current position
Set found = (current position < length AND item equals current component) |
|
|
|
|
|
|
|
|
This search function needs the same parameters as the previous one. To the function precondition we must add the requirement that the list is already sorted. |
|
|
|
|
|