|
|
|
|
|
|
|
We need to keep track of the first possible place to look (first) and the last possible place to look (last). At any one time, we are looking only in list[first] through list[last]. When the function begins, first is set to 0 and last is set to length-1. |
|
|
|
|
|
|
|
|
This function needs the same five parameters as the previous search functions: the array containing the list, the item, the length of the list, a Boolean flag that tells whether the item was found, and the position of the item in the list (if it is there). |
|
|
|
|
|
|
|
|
void BinSearch(
/* 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 <= INT_MAX / 2
// && list[0..length-1] are in ascending order
// && item is assigned
// Postcondition:
// IF item is in list
// found == TRUE && list[index] == 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 (item < list[middle])
// Assert: item is not in list[middle..last]
last = middle - 1;
else if (item > list[middle])
// Assert: item is not in list[first..middle]
first = middle + 1; |
|
|
|
|
|