|
|
|
|
|
|
|
/* out */ Boolean& found ) // True if item is found
// Searches list for item, returning the index if item was found.
// Precondition:
// length <= INT_MAX / 2
// && list[0..length-1] are in ascending order
// && item is assigned
// Postcondition:
// IF item is in list
// found == TRUE && list[index] contains item
// ELSE
// found == FALSE && index is undefined
{
int first = 0; // Lower bound on list
int last = length - 1; // Upper bound on list
int middle; // Middle index
found = FALSE;
while (last >= first &&!found)
{
// Invariant (prior to test):
// If item is in list[0..length-1] then
// item is in list[first..last]
middle = (first + last) / 2;
if (strcmp(item, list[middle]) < 0)
// Assert: item is not in list[middle..last]
last = middle - 1;
else if (strcmp(item, list[middle]) > 0)
// Assert: item is not in list[first..middle]
first = middle + 1;
else
// Assert: item is in list[middle]
found = TRUE;
}
index = middle;
}
//******************************************************************
void Print(
/* in */ const String10 student[], // List of students
/* in */ const Boolean isPresent[], // Check mark list
/* in */ int length ) // Length of lists |
|
|
|
|
|