Binary Search: Dealing with the edge

This is a discussion on Binary Search: Dealing with the edge within the C++ Programming forums, part of the General Programming Boards category; Is it me? I must be a little slow. I've just noticed something, and I made a little program that ...

  1. #1
    Registered User whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    7,709

    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?

  2. #2
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,893
    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;
    }
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  3. #3
    Registered User whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    7,709
    That it does. Thanks for showing me that CornedBee! And yeah, gotta learn the standard function too.

  4. #4
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,305
    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.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  5. #5
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,046
    It's tough to program a working binary search. Don't worry, you're not alone.
    http://www.cprogramming.com/tutorial...earchbugs.html
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. How to search within a binary file
    By khpuce in forum C Programming
    Replies: 17
    Last Post: 04-12-2005, 05:23 AM
  2. searching and insertion in a binary search tree
    By galmca in forum C Programming
    Replies: 1
    Last Post: 03-26-2005, 04:15 PM
  3. binary search or linear search
    By vajira in forum C Programming
    Replies: 0
    Last Post: 06-05-2003, 12:42 PM
  4. Ornery binary search algorithm
    By Unregistered in forum C Programming
    Replies: 3
    Last Post: 11-17-2001, 02:32 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21