Searching For Closest float values in an array

I have a problem trying to pick the closest float value out of an array. Here is some example data;

The numbers that I will be dealing with always share this mirroring characteristic.

{-9,-3,-1,0,1,3,9}

If I search for -8.8 I would expect to be returned -9.

If I searched for 8.8 I would expect to be returned 9.

In the past when searching arrays for closest values I would go through the array keeping track of the absolute value for each array element minus the value I wanted. The Smallest value would win.

That method presents a problem here for me tho because at least 2 numbers in the array would be "closest" (in my above example 9 & -9)

Answers


your array will always be sorted, so binary search should be amenable to reduce the candidate set to 2 array values at max. i can only conceive of one challenge which will arise if the original array contains floats some of which differ by less than the machine precision.

how to deal best with this situation will depend on your application (if it isn't esoteric in the first place); note however that all the values indistinguishable from your test value will form a contiguous subsequence in your array, so as a heuristic you might just pick the middle element of this subsequence.


The fact that your array is mirrored makes this easy. You can initially ignore the sign of your search value and, as you mentioned, just find the closest absolute value. Then fix the sign.

This is Python, but it should be close enough to pseudocode that you can translate it to whatever you need.

def find_closest(search_val):
    smallest_diff = float(inf)
    closest_val = 0
    # Search only positive half of array
    for val in [0, 1, 3, 9]:
        # Treat search_val as positive for now
        diff = abs(val - abs(search_val))
        if diff < smallest_diff:
            smallest_diff = diff
            closest_val = val
    # Correct sign of result
    if search_val < 0:
        closest_val = -closest_val
    return closest_val

Since, as you have mentioned, your numbers are always mirrored around zero, then only examine the negative numbers (assuming that you array is sorted). You will avoid the mentioned problem. What about 0.5? It too has two numbers that are at equal distance. How would you break the tie?


Need Your Help

Can FactoryGirl set a variable each time an instance is generated?

ruby-on-rails ruby ruby-on-rails-4 factory-girl

I am trying assign an array of a new public and private key to a variable for each instance so I can generate a unique and matching bitcoin address and signature.

AppDomain.AssemblyLoad event catches all exceptions raised within the event handlers

c# .net exception-handling appdomain .net-assembly

It seems the .NET AppDomain.AssemblyLoad event catches any exceptions thrown within it's event handlers, not propagating them to the caller who triggered the assembly load (e.g. Assembly.LoadFile()...

About UNIX Resources Network

Original, collect and organize Developers related documents, information and materials, contains jQuery, Html, CSS, MySQL, .NET, ASP.NET, SQL, objective-c, iPhone, Ruby on Rails, C, SQL Server, Ruby, Arrays, Regex, ASP.NET MVC, WPF, XML, Ajax, DataBase, and so on.