0

I need Help!

Consider this following modified version of the binary search algorithm. (Modifications are indicated by a comment highlighted asterisks.) With this new version of the binary search algorithmn work correctly for all data? If not, specify a situiation in which this version will fail.

template<class element, class Keytype>
bool binarySearch(const apvector<element> &list, int n, Keytype target, element &object)

{
int low, middle, high;
bool found = false;

low = 0;
high = n;
while ((low <= high) && ! found)
{
middle = (low + high) / 2;
if(list[middle] = target)
found=true;
else if (list[middle] < target)
low = middle;  // *** MODIFICATION HERE ***
else
high = middle; // *** MODIFICATION HERE ***
}
if (found)
object=list[middle];
return found;
}
2
Contributors
2
Replies
3
Views
8 Years
Discussion Span
Last Post by saintrenz
0

1) Line 13 is wrong. It should use the == boolean operator, not the = assignment operator.

>>If not, specify a situiation in which this version will fail.

I can think of three kinds of data for which that algorithm will fail. If you think about the different kinds of data then you should be able to list at least one of them too.

Edited by Ancient Dragon: n/a

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.