Efficient way to find closest float in an array?

Unity Engine
1

Hi all,

I’m having a little trouble with this problem and I was wondering if anyone could help me out?
I have a float value and I’m trying to find the nearest value out of an array of float values.
At the moment I am looking through the array and finding any element that is under a certain threshold but this seems like a really inefficient way to figure this out.
Just wondering, does anyone know a good way to approach this?

Thanks,
Pete

2

Are the values in the array sorted? You can use ArrayBinarySearch if it is. Should be pretty quick.

1 Like
3

I don’t know if c# has any native way of filling the array as sorted. But one algorithm of doing this could be this

4

What does that mean, exactly?

I’d start with the simplest and optimize if necessary:floats.OrderBy(f => Mathf.Abs(n - f)).First()

5

Given an array of floats and a target float, you want to find the closest float to the target float in the array.

As shaderop said, you can use binary search with a sorted array. This will trade insertion speed for search speed. If you search more than you insert, this will be ideal. There are a few ways to implement a sorted list each with different trade-offs. Otherwise, you will have to brute force as you are currently doing.

6

n comparisons for n values seems appropriate if you’re changing the contents of the array very often.

If you’re not changing the contents of the array [very often], you can use the sort/binary search mentioned.

If the float you’re checking is from the array itself, then sorting the array based on distance, comparing the left and right neighbors of the float’s original index (or only retrieving one if you’re at the 0 or array.Length - 1 index) and returning the one with the smallest distance between the two would be better, though that is assuming you’re using a float value from the array itself and once again assuming you’re not changing the contents of the array very often.

7

I had a bit of success searching the neighbours first, it seems to have made the whole thing a lot lighter.
Thanks heaps for all the pointers!

Pete