Determine an index of a closest number in a database, from a user's input

Hello people!

I need to build a class to hold different float values. I will use it’s instance to provide 3 integers closest to the argument a user supplied to it.

The first output number (center one) is considered to have a closest value to the input argument. The other 2 ones are the “2nd closest” to the input value. Like this: 2 <---- 1 ----> 2 . Then, I will return an object, which will store 3 variables as closest (1), first neighbor (2) and second neighbor(3).

Now, for example, the user supplied 2.2f .

The data held is as follows (was pre-filtered to be from lowest to greatest):

0.1f;

2.05f;

3.0f;

4.6f

4.65f;

How can I arrange my structure so that I can see that the number supplied is closest to 2.05f, return this 2.05f, plus 0.1f and 3.0f as its 2 neighbors?

The thing is, I don’t want to iterate through the list or whatever it could be, until I will find the closest value. If possible, I would want to immediately figure out 2.05 is sitting on the 2nd space, 0.1 is on the first one and 3.0 is the third one. This somewhat reminds me of Dictionary when I think of it.

Any ideas on how to return a cell index which contains the closest number to the input one? How should I build my class to make it possible?

Thank you

What you want here is almost certainly to binary search.

There are two common approaches which are essentially identical - use an ordered array or a (binary) tree data structure (an ordered array can be considered an encoding for a binary tree - which is itself one possible encoding of an nary-tree - and vice versa for both of those relations).

The ordered array approach is probably most suitable here, since once you know the index you can use -1 and +1 to get the neighbours.

I will not bore you with the detail of the binary search but instead refer you to Array.BinarySearch and Array.Sort which will enable you to implement this without knowing the implementation details yourself.

As an aside you may be reminded of Dictionary because of its fast lookups - a simple but completely generic way to implement a dictionary is with a binary tree where the key used is some kind of orderable hash of the dictionary key type (e.g. the GetHashCode function implemented on all .NET objects).