|
|
|
|
|
|
|
void SearchOrd(
/* inout */ 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. If item was not found, SearchOrd returns the index where
// item belongs.
// Precondition:
// length < MAX_LENGTH
// && list[0..length-1] are in ascending order
// && item is assigned
// Postcondition:
// list is the same as list@entry except that list[length] is
// overwritten to aid in the search
// && IF item is in list@entry
// found == TRUE && list[index] == item
// ELSE
// found == FALSE && index is where item belongs
{
index = 0;
// Store item at position beyond end of list
list[length] = item;
// Exit loop when item is found, perhaps as sentinel
while (item > list[index])
// Invariant (prior to test):
// item is not in list[0..index-1]
index++;
// Determine whether item was found prior to sentinel
found = (index < length && item == list[index]);
} |
|
|
|
|
|
|
|
|
On average, searching an ordered list in this way takes the same number of iterations to find an item as searching an unordered list. The advantage of this new algorithm is that we find out sooner if an item is missing. Thus, it is slightly more efficient; however, it works only on a sorted list. |
|
|
|
|
|