CODEWITHSUNDEEP
c#arraysfind
user1328639
user1328639

Reputation: 501

finding closest value in an array

int[] array = new int[5]{5,7,8,15,20};

int TargetNumber = 13;

For a target number, I want to find the closest number in an array. For example, when the target number is 13, the closest number to it in the array above is 15. How would I accomplish that programmatically in C#?

Upvotes: 44

Views: 73481

Answers (6)

Samuel Lehikoinen
Samuel Lehikoinen

Reputation: 9

If you need to find the closest value to the average

very open style

public static double Miidi(double[] list)
{
    bool isEmpty = !list.Any();
    if (isEmpty)
    {
        return 0;
    }
    else
    {
        double avg = list.Average();
        double closest = 100;
        double shortest = 100;
        {
            for ( int i = 0; i < list.Length; i++)
            {
                double lgth = list[i] - avg;
                if (lgth < 0)
                {
                    lgth = lgth - (2 * lgth);
                }
                else
                    lgth = list[i] - avg;

                if (lgth < shortest)
                {
                    shortest = lgth;
                    closest = list[i];
                }
            }
        }

        return closest;
    }
}

Upvotes: 0

Jon Skeet
Jon Skeet

Reputation: 1500903

EDIT: Have adjusted the queries below to convert to using long arithmetic, so that we avoid overflow issues.

I would probably use MoreLINQ's MinBy method:

var nearest = array.MinBy(x => Math.Abs((long) x - targetNumber));

Or you could just use:

var nearest = array.OrderBy(x => Math.Abs((long) x - targetNumber)).First();

... but that will sort the whole collection, which you really don't need. It won't make much difference for a small array, admittedly... but it just doesn't feel quite right, compared with describing what you're actually trying to do: find the element with the minimum value according to some function.

Note that both of these will fail if the array is empty, so you should check for that first.

Upvotes: 78

NilesDavis
NilesDavis

Reputation: 69

I found this really sexy approach years ago in Math.NET Numerics https://numerics.mathdotnet.com/ which works with BinarySearch in the array. It was a good help in preparation for interpolations and works down to .Net 2.0:

public static int LeftSegmentIndex(double[] array, double t)
{
    int index = Array.BinarySearch(array, t);
    if (index < 0)
    {
        index = ~index - 1;
    }
    return Math.Min(Math.Max(index, 0), array.Length - 2);
}

Upvotes: 5

Amit Srivastava
Amit Srivastava

Reputation: 51

Performance wise custom code will be more useful. 

public static int FindNearest(int targetNumber, IEnumerable<int> collection) {
    var results = collection.ToArray();
    int nearestValue;
    if (results.Any(ab => ab == targetNumber))
        nearestValue = results.FirstOrDefault(i => i == targetNumber);
    else{
        int greaterThanTarget = 0;
        int lessThanTarget = 0;
        if (results.Any(ab => ab > targetNumber)) {
            greaterThanTarget = results.Where(i => i > targetNumber).Min();
        }
        if (results.Any(ab => ab < targetNumber)) {
            lessThanTarget = results.Where(i => i < targetNumber).Max();
        }

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

Upvotes: -1

Lee Grissom
Lee Grissom

Reputation: 9953

Both Jon and Rich gave great answers with MinBy and ClosestTo. But I would never recommend using OrderBy if your intent is to find a single element. It's far too inefficient for those kinds of tasks. It's simply the wrong tool for the job.

Here's a technique that performs marginally better than MinBy, is already included in the .NET framework, but less elegant than MinBy: Aggregate

var nearest = array.Aggregate((current, next) => Math.Abs((long)current - targetNumber) < Math.Abs((long)next - targetNumber) ? current : next);

As I said, not as elegant as Jon's method, but viable.

Performance on my computer:

  1. For(each) Loops = fastest
  2. Aggregate = 2.5x slower than loops
  3. MinBy = 3.5x slower than loops
  4. OrderBy = 12x slower than loops

Upvotes: 25

Rich O&#39;Kelly
Rich O&#39;Kelly

Reputation: 41767

If you're using .Net 3.5 or above LINQ can help you here:

var closest = array.OrderBy(v => Math.Abs((long)v - targetNumber)).First();

Alternatively, you could write your own extension method:

public static int ClosestTo(this IEnumerable<int> collection, int target)
{
    // NB Method will return int.MaxValue for a sequence containing no elements.
    // Apply any defensive coding here as necessary.
    var closest = int.MaxValue;
    var minDifference = int.MaxValue;
    foreach (var element in collection)
    {
        var difference = Math.Abs((long)element - target);
        if (minDifference > difference)
        {
            minDifference = (int)difference;
            closest = element;
        }
    }

    return closest;
}

Useable like so:

var closest = array.ClosestTo(targetNumber);

Upvotes: 35

Related Questions