How do I find the closest array element to an arbitrary (non-member) number?

Question

Seemingly similar questions: "Finding closest number in an array" (in Java) and "find nearest match to array of doubles" (actually a geography problem).

I have a (sorted) array of doubles. Given an arbitrary number (which may or may not be an exact match for one of the array elements), how can I return the index of the number which is the closest match?

For example, using the following array:

• 1.8
• 2.4
• 2.7
• 3.1
• 4.5

Querying 2.5 would return with an index of 1, corresponding to the value of 2.4.

Bonus points for detecting values that lie completely outside of the range of the array elements. For example, using the array listed above, your code may decide that 4.6 is in, but 5.9 is out. If you want to try this part of the question, the specifics are in your hands.

Selfjustifying

possible duplicate of Finding closest match in collection of numbers – Multifoliate

Answer 1

Array.BinarySearch, which returns:

The index of the specified value in the specified array, if value is found. If value is not found and value is less than one or more elements in array, a negative number which is the bitwise complement of the index of the first element that is larger than value. If value is not found and value is greater than any of the elements in array, a negative number which is the bitwise complement of (the index of the last element plus 1).

Now that won't get you 100% of the way there, since you'll know the number is either less than or greater than the match, but it really only leaves you with two indices to check.

Marr

Answer 2

One way to do this using LINQ is like this:

public int GetClosestIndex( List<double> doublelist, double targetvalue )
{
  return doublelist.IndexOf(doublelist.OrderBy(d => Math.Abs(d - targetvalue)).ElementAt(0));
}

It might have some performance issues, but If the list is not that long, it should not pose a problem. Also, if two elements are equally distant from the target value, it will return the first index of those.

Bjork

@Steven - Thanks. Quite similar in approach to your own ;) – Watterson

@Øyvind: And you we 22 seconds faster than me :'( – Usher

Answer 3

Perhaps not the fastest solution, but certainly pleasant eye-candy:

double search;
double[] array;

var nearest = (
    from value in array
    orderby Math.Abs(value - search)
    select value).First();

var index = array.IndexOf(nearest);

Note that this will absolutely be slower than a binary search algorithm, because it need to process each element in the array and sorting means building a hash table of those items.

Usher

Note that he is asking for the index of the closest value, and not the closest value itself. – Watterson

It's a nice approach though :) – Selfjustifying

@Tom: Of course no were near the performance characteristics of Mark's answer. That's why he got my +1. – Usher

Answer 4

Something like this:

double[] values = new double[]
{
    1.8,
    2.4,
    2.7,
    3.1,
    4.5
};

double difference = double.PositiveInfinity;
int index = -1;

double input = 2.5;

for (int i = 0; i < values.Length; i++)
{
    double currentDifference = Math.Abs(values[i] - input);

    if (currentDifference < difference)
    {
        difference = currentDifference;
        index = i;
    }

    // Stop searching when we've encountered a value larger
    // than the inpt because the values array is sorted.
    if (values[i] > input)
        break;
}

Console.WriteLine("Found index: {0} value {1}", index, values[index]);

Bluefield

Answer 5

List<int> results;
int target = 0;
int nearestValue = 0;
if (results.Any(ab => ab == target)) {
    nearestValue= results.FirstOrDefault<int>(i => i == target);
} else {
    int greaterThanTarget = 0;
    int lessThanTarget = 0;
    if (results.Any(ab => ab > target) {
        greaterThanTarget = results.Where<int>(i => i > target).Min();
    }

    if (results.Any(ab => ab < target)) {
        lessThanTarget = results.Where<int>(i => i < target).Max();
    }

    if (lessThanTarget == 0 ) {
        nearestValue= greaterThanTarget;
    } else if (greaterThanTarget == 0) {
        nearestValue = lessThanTarget;
    } else {
        if (target - lessThanTarget < greaterThanTarget - target) {
            nearestValue = lessThanTarget;
        } else {
            nearestValue = greaterThanTarget;
        }
    }
}

Terpsichorean

Please, provide some comment, some description of your contribution – Reticle