View more

View more

View more

### Image of the Day Submit

IOTD | Top Screenshots

### The latest, straight to your Inbox.

Subscribe to GameDev.net Direct to receive the latest updates and exclusive content.

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

13 replies to this topic

### #1gasto  Members

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.

### #2fastcall22  Moderators

Posted 11 April 2014 - 06:46 PM

POPULAR

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.

zlib: eJzVVLsSAiEQ6/1qCwoK i7PxA/2S2zMOZljYB1TO ZG7OhUtiduH9egZQCJH9 KcJyo4Wq9t0/RXkKmjx+ cgU4FIMWHhKCU+o/Nx2R LEPgQWLtnfcErbiEl0u4 0UrMghhZewgYcptoEF42 YMj+Z1kg+bVvqxhyo17h nUf+h4b2W4bR4XO01TJ7 qFNzA7jjbxyL71Avh6Tv odnFk4hnxxAf4w6496Kd OgH7/RxC

### #3Buckeye  GDNet+

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.

You don't forget how to play when you grow old; you grow old when you forget how to play.

### #4Álvaro  Members

Posted 11 April 2014 - 07:34 PM

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

### #5Ectara  Members

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.

### #6Hodgman  Moderators

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.

### #7iMalc  Members

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

### #8gasto  Members

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.

### #9Buckeye  GDNet+

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.

You don't forget how to play when you grow old; you grow old when you forget how to play.

### #10gasto  Members

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.

### #11NightCreature83  Members

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, theHunter, theHunter: Primal, Mad Max

### #12DiegoSLTS  Members

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.

### #13Hodgman  Moderators

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

### #14Waterlimon  Members

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.