Jump to content
  • Advertisement
Sign in to follow this  
gasto

Binary search implementation

This topic is 2011 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I did not consult any reference for this implementation, so I guess there are bugs lurking everywhere.

 

Constructive criticisms welcome. And yes, it is C-ish.

 
int BinarySearch(int data[], unsigned int elements, int key)
{
    if(elements==0)
    {
        cerr << "Binary search not able to perform on 0 element array";
        exit(-1);
    }
    unsigned int half_offset = elements<<31? (elements-1)/2 : elements/2;   // truncation will happen anyway.
    unsigned int current_index = elements<<31? (elements-1)/2 : elements/2; // Non portable bitwise ops.
    
        
    while(half_offset!=0)
    {
        if(data[current_index]==key)
            return current_index;
        else if(data[current_index]<key)
        {
            current_index += half_offset<<31? (half_offset+1)/2 : half_offset/2;
        }
        else if(data[current_index]>key)
        {
            current_index -= half_offset<<31? (half_offset+1)/2 : half_offset/2;
        }
        half_offset /= 2; // Truncated to floor
    }
    if(data[current_index]==key)
                return current_index;
}
Edited by gasto

Share this post


Link to post
Share on other sites
Advertisement

Is that code snippet complete? You should be getting an error that not all paths return a value. You end the function on an if-statement. I.e., when execution drops through the IF, there's no return value.

Share this post


Link to post
Share on other sites


// Non portable bitwise ops.

Moreover, if you were to test for even or odd numbers (though, as pointed out, it isn't necessary), wouldn't it be easier (and more portable) to AND with 1 like so: (x & 1)? I think that communicates clearer intent.

Share this post


Link to post
Share on other sites
Fastcall said everything that I was going to say. Not sure why his post was -1'ed.

x&1 or x%2 are the idiomatic ways of checking if an int is odd/even. The shift by 31 trick is much more confusing (and unecessary here).

As mentioned by Buckeye, you need a return -1; etc to handle the failure case.

Share this post


Link to post
Share on other sites

Corrected according to feedback:

 
unsigned int BinarySearch(int data[], unsigned int elements, int key)
{
    if(elements==0)
    {
        cerr << "Binary search not able to perform on 0 element array";
        exit(-1);
    }
    unsigned int half_offset = elements/2 /*upper half smaller when even elements*/;
    unsigned int current_index = elements/2; 
    
        
    while(half_offset!=0)
    {
        if(data[current_index]==key)
            return current_index;
        else if(data[current_index]<key)
        {
            current_index += (half_offset+1)/2;
        }
        else if(data[current_index]>key)
        {
            current_index -= (half_offset+1)/2;
        }
        half_offset /= 2; // Truncated to floor
    }
    if(data[current_index]==key)
                return current_index;
    else
        cerr << "Finished array search without any matching results";
}
Edited by gasto

Share this post


Link to post
Share on other sites
    if(data[current_index]==key)
                return current_index;
    else
        cerr << "Finished array search without any matching results";
    return <fail-value>; // perhaps -1 as suggested above
}

As mentioned before, you need to add a return <value> before the closing brace.

Edited by Buckeye

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!