Is it me? I must be a little slow. I've just noticed something, and I made a little program that demonstrates my point:
Code:
#include <iostream>
#include <cstddef>
int *binary_search( int list[], std::size_t length, int value ) {
std::size_t
hi_end = length - 1,
low_end = 0,
midpoint;
while( low_end <= hi_end ) {
midpoint = low_end + (hi_end - low_end) / 2;
if( value == list[midpoint] )
return &list[midpoint];
else if( value < list[midpoint] )
hi_end = midpoint - 1;
else
low_end = midpoint + 1;
}
return NULL;
}
int main( )
{
int *series = NULL;
std::size_t length = 0;
std::cout <<"Enter a length for the series:\n";
std::cin >>length;
if( length > 0 ) {
series = new int[length];
if( series ) {
for( std::size_t i = 0; i < length; i++ )
series[i] = static_cast< int >( i + 1 );
int find_it = 0;
std::cout <<"Enter a search item:\n";
std::cin >>find_it;
int *match = binary_search( series, length, find_it );
if( match )
std::cout <<"Found a match for " <<*match <<".\n";
else
std::cout <<"Sorry, no match.\n";
delete[] series;
} else {
std::cout <<"Failed to allocate space for the series.\n";
}
} else {
std::cout <<"Invalid length value. Try again.\n";
}
}
Sorry if it's a little messy.
Anyway, I wrote that earlier today and realized that if I tried to search for 0 in a list of 2 or more elements, it breaks horribly, but not all the time. If you put a negative number in there then binary search is happy again and can return a failed search without crashing the program.
I figured out why it crashes at least. hi_end eventually underflows and causes problems. But the real question is if I have cause to be concerned. It seems silly that you can't search for zero amongst a list of positive integers, risking failure. What do smart people do?