Thread: 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?

That it does. Thanks for showing me that CornedBee! And yeah, gotta learn the standard function too.