Jump to content

  • Log In with Google      Sign In   
  • Create Account

Binary search implementation


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
13 replies to this topic

#1 gasto   Members   -  Reputation: 261

Like
0Likes
Like

Posted 11 April 2014 - 06:22 PM

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, 11 April 2014 - 06:23 PM.

Intel Core 2 Quad CPU Q6600, 2.4 GHz. 3GB RAM. ATI Radeon HD 3400.

Sponsor:

#2 fastcall22   Crossbones+   -  Reputation: 4346

Like
10Likes
Like

Posted 11 April 2014 - 06:46 PM

There's no need to check if a number is odd prior to do integer division: 10/2 == 11/2 == 5.
There also isn't any need to check if a number is odd to do integer division, rounding up: (12+1)/2 == (11+1)/2 == 6.
Shifting by 31 bits to determine if the first bit is set has the potential of breaking, if unsigned int isn't 32-bits. It is more idiomatic to check if an integer is odd by testing its first bit: elements&1 ? odd : even.

Also, the standard library provides a binary search algorithm, lower_bound.

Edited by fastcall22, 11 April 2014 - 06:50 PM.

c3RhdGljIGNoYXIgeW91cl9tb21bMVVMTCA8PCA2NF07CnNwcmludGYoeW91cl9tb20sICJpcyBmYXQiKTs=

#3 Buckeye   Crossbones+   -  Reputation: 5070

Like
0Likes
Like

Posted 11 April 2014 - 07:02 PM

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.


Please don't PM me with questions. Post them in the forums for everyone's benefit, and I can embarrass myself publicly.


#4 Álvaro   Crossbones+   -  Reputation: 13368

Like
2Likes
Like

Posted 11 April 2014 - 07:34 PM

There is an implementation of binary search in the library: upper_bound

#5 Ectara   Crossbones+   -  Reputation: 2981

Like
0Likes
Like

Posted 11 April 2014 - 11:01 PM


// 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.



#6 Hodgman   Moderators   -  Reputation: 30432

Like
4Likes
Like

Posted 11 April 2014 - 11:23 PM

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.

#7 iMalc   Crossbones+   -  Reputation: 2306

Like
0Likes
Like

Posted 12 April 2014 - 03:40 AM

There are several unusual things you are doing there.

I discussed binary search and how to do it better, in this article that I wrote about various searching techniques:

http://homepages.ihug.co.nz/~aurora76/Malc/Searching.htm


"In order to understand recursion, you must first understand recursion."
My website dedicated to sorting algorithms

#8 gasto   Members   -  Reputation: 261

Like
0Likes
Like

Posted 12 April 2014 - 09:09 AM

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, 12 April 2014 - 09:10 AM.

Intel Core 2 Quad CPU Q6600, 2.4 GHz. 3GB RAM. ATI Radeon HD 3400.

#9 Buckeye   Crossbones+   -  Reputation: 5070

Like
0Likes
Like

Posted 12 April 2014 - 10:21 AM

    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, 12 April 2014 - 10:23 AM.

Please don't PM me with questions. Post them in the forums for everyone's benefit, and I can embarrass myself publicly.


#10 gasto   Members   -  Reputation: 261

Like
0Likes
Like

Posted 12 April 2014 - 06:19 PM

How do I choose a failure value in an unsigned int?


Intel Core 2 Quad CPU Q6600, 2.4 GHz. 3GB RAM. ATI Radeon HD 3400.

#11 NightCreature83   Crossbones+   -  Reputation: 2845

Like
0Likes
Like

Posted 12 April 2014 - 06:22 PM

you should replace your exit call with a return to be honest, you dont want to terminate the application when this function fails. Instead just return -1 because its very unlikely you are going to find your element at max uint. The calling code knows how big the array is anyway so if max uint is a valid return value the calling code can determine this.


Edited by NightCreature83, 12 April 2014 - 06:23 PM.

Worked on titles: CMR:DiRT2, DiRT 3, DiRT: Showdown, GRID 2, Mad Max

#12 DiegoSLTS   Members   -  Reputation: 1437

Like
0Likes
Like

Posted 12 April 2014 - 06:33 PM

How do I choose a failure value in an unsigned int?

Maybe you can return a value higher than the array size (elements+1) and when you call that function always check if the return value is less than elements. It might work if you know you won't have gigant arrays as input. It doesn't sound very intuitive maybe, but if you can't change the return type of the function you'll have setup a convention.

 

Anyway, it's not THAT werid since some functions that work over collections do a similar thing. Look at std::find, if the value can't be found it returns "last", which is a parameter you must supply to that function instead of a constant error value, then when you call std::find you always do something like:

returnedValue = std::find(array.begin(),array.end(),value);
if ( returnedValue  != array.end() )
{
    // something
}

Edited by DiegoSLTS, 12 April 2014 - 06:36 PM.


#13 Hodgman   Moderators   -  Reputation: 30432

Like
3Likes
Like

Posted 12 April 2014 - 07:49 PM

Yeah there's two common conventions: for stuff that's based around iterators, the standard idiom is returning 'end' (index of last item + 1, same as size), or the other common idiom is returning an obviously invalid value, such as NULL for pointers, -1 for ints, or max value for unsigned (though it should probably be signed, forcing the user to cast to unsigned, as a reminder that they should also check for -1).

#14 Waterlimon   Crossbones+   -  Reputation: 2574

Like
0Likes
Like

Posted 13 April 2014 - 03:03 AM

You can also take the return value as a parameter and return a bool for success.

o3o





Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS