|
|
|
|
|
|
|
// 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:
// 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 == length
{
index = 0;
list[length] = item; // Store item at position beyond
// end of list
while (item != list[index])
// Invariant (prior to test):
// item is not in list[0..index-1]
index++;
found = (index < length);
} |
|
|
|
|
|
|
|
|
The Search and Search2 algorithms both assume that the list to be searched is unordered. A drawback to searching an unordered list is that we must scan the entire list to discover that the search item is not there. Think what it would be like if your city telephone book contained people's names in random rather than alphabetical order. To look up Mary Anthony's phone number, you would have to start with the first name in the phone book and scan sequentially, page after page, until you found it. In the worst case, you might have to examine tens of thousands of names only to find out that Mary's name is not in the book. |
|
|
|
|
|
|
|
|
Of course, telephone books are alphabetized, and the alphabetical ordering makes searching easier. If Mary Anthony's name is not in the book, you discover this fact quickly by starting with the A's and stopping the search as soon as you have passed the place where her name should be. In software development, arranging list items into order is a very common operation on lists. For example, we might want to put a list of stock numbers into either ascending or descending order, or we might want to put a list of words into alphabetical order. Arranging values into order is known as sorting. |
|
|
|
|
|