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?

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;
}

---

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

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.

It's tough to program a working binary search. Don't worry, you're not alone. :)
http://www.cprogramming.com/tutorial...earchbugs.html