Searching... Binary Search

Kimi · Joined: 30 Jan 2005 Posts: 23 Location: Argentina

Hello... how are you

I have a litlle listo of elemtents stored in a external ram....lets say 26000 floatant numbers... (and I really have this number...jajaja). Also I have an index that sort them from the smallest to the biggest. Everything in a kind of table form...

Register Float Order

0 1.024 2
1 0.24 1
2 -4.28 0
3 7.44 3

Mi idea is to look for a number in the table, but as this numbers are float, I will "never" get the same number, so my function has to return the two "nearest" numbers... In the example, I will try to search for 0.5, As 0.5 is not on the table, the function has to "return" (or set two global variables) with 1.024 and 0.24.

I tried something like a binary search (don't have the code hear, but it was a binary search) and only worked if the number given was in the table...so never returned the two nearest numbers as I want.

Anybody has an idea where I can look for this algorithm? or how can I do it?

Thanks very much

Kimi

libor · Joined: 14 Dec 2004 Posts: 288 Location: Hungary

If you have a binary search algorithm, this is what you need, you only have to stop the loop before the last step (before it actually wants to find the exact value) and return the two values with adjacent indexes.

Kimi · Joined: 30 Jan 2005 Posts: 23 Location: Argentina

but it's not working...don't know why... if somebody has a code...or and idea...please post it!
Thanks

libor · Joined: 14 Dec 2004 Posts: 288 Location: Hungary

Are these 26000 numbers in the table constants? Or do you need to change then on the fly?
Why dont you store them already sorted? No index would be required their position in RAM would be the index, your search algorithm would be much easier and faster.

Douglas Kennedy · Joined: 07 Sep 2003 Posts: 755 Location: Florida

The binary sort will work just fine but with a twist for float numbers.Since floats are normalized ( sign 23 bits and 8 bit exponent with 127 offset ) the sign needs to be searched first followed by the exponent then the 23 bit mantissa ( remember 0.5 ,0.25,0.125 will have the same mantissa )
If most of the 26000 numbers are the same from binary search to binary search then storing them in order or a hashing them into a type of contents addressable table will improve speed as suggested in an earlier post.