|
|
|
|
|
|
|
3. The item being searched for |
|
|
|
|
|
|
|
|
4. A flag telling whether or not the search was successful |
|
|
|
|
|
|
|
|
5. The index indicating where the item was located (if found) |
|
|
|
|
|
|
|
|
The array containing the list is made up of components of type ItemType. |
|
|
|
|
|
|
|
|
We call the array list and the item being searched for item. The variables length, found, and index serve the same purposes here as they did in the ScanList function; that is, length is the number of filled components in the list array, found tells whether the item is in list, and index gives the location of item if it is present in list. |
|
|
|
|
|
|
|
|
Note that the two outgoing parameters, index and found, are redundant. The index parameter would be sufficient because the calling routine could check to see if index is greater than length-1. If it is, then item was not found. We keep this redundancy, however, for clarity. |
|
|
|
|
|
|
|
|
#include "bool.h" // For Boolean type
.
.
.
void Search(
/* in */ const ItemType list[], // List to be searched
/* in */ ItemType item, // Item to be found
/* in */ int length, // Length of list
/* out */ int& index, // Location of item if found
/* out */ Boolean& found ) // True if item is found
// Searches list for item, returning the index
// of item if item was found
// Precondition:
// length <= MAX_LENGTH
// && list[0..length-1] are assigned && item is assigned
// Postcondition:
// IF item is in list
// found == TRUE && list[index] == item
// ELSE
// found == FALSE && index == length
{
index = 0;
while (index < length && item != list[index])
// Invariant (prior to test):
// item is not in list[0..index-1]
// && 0 <= index <= length
index++;
found = (index < length);
} |
|
|
|
|
|