Binary Search: Dealing with the edge

• 10-11-2007
whiteflags
Binary Search: Dealing with the edge
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?
• 10-11-2007
CornedBee
Smart people use std::binary_search ;)

That said, this works:
Code:

```int *binary_search( int list[], std::size_t length, int value ) {     std::size_t         hi_end = length,         low_end = 0,         midpoint;     while( low_end < hi_end ) {         midpoint = low_end + (hi_end - low_end - 1) / 2;         if( value == list[midpoint] ) {             return &list[midpoint];         } else if( value < list[midpoint] ) {             hi_end = midpoint;         } else {             low_end = midpoint + 1;                 }     }     return NULL; }```
• 10-11-2007
whiteflags
That it does. :) Thanks for showing me that CornedBee! And yeah, gotta learn the standard function too.
• 10-12-2007
iMalc
You might want to read my article about searching, which primarily focuses on binary search, and how to write one in such a way as to make it about twice as fast as typical implementations. It is accessible from the link in my sig.

Then I suggest you simply use std::lower_bound and be done with it.
• 10-13-2007
dwks
It's tough to program a working binary search. Don't worry, you're not alone. :)
http://www.cprogramming.com/tutorial...earchbugs.html