在数组中查找最接近的值

Question

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

int TargetNumber = 13;

我想在一个数组中找到距离目标数最接近的数。例如，当目标数为13时，在上面的数组中最接近它的数是15。我该如何在C#中以编程方式实现这一点？

- user1328639

Answer 1

编辑: 调整了以下查询，采用 long 算术来避免溢出问题。

我可能会使用MoreLINQ的MinBy方法：

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

或者你可以直接使用：

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

...但是那将会对整个集合进行排序，而这并不是你需要的。诚然，对于一个小数组来说，这并不会有太大的区别......但是相比于描述你实际尝试做的事情：根据一些函数找到具有最小值的元素，这样做感觉还是不太对。

请注意，如果数组为空，这两种方法都会失败，所以你应该先检查数组是否为空。

- Jon Skeet

---

@JonSkeet 有没有办法修改 MinBy 版本，使其返回索引而不是值？ - ManInMoon

@ManInMoon：最简单的方法是使用Select((value, index) => new { Value, Index })开始，然后MinBy将返回包含最小值的对，您可以通过这种方式获取索引。 - Jon Skeet

如果我想不止一次地找到最接近的数字，会有什么变化吗？而且我不想为每个要查找的数字调用 OrderBy。 - rraszewski

如果数组可能很大，我会使用二分查找，前提是输入的数组实际上已经排序。这需要更多的代码，但效率更高。 - Jon Skeet

Answer 2

如果你使用的是 .Net 3.5 或更高版本，LINQ 可以帮助你：

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

或者，您可以编写自己的扩展方法：

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;
}

可以这样使用：

var closest = array.ClosestTo(targetNumber);

- Rich O'Kelly

---

值得一提的是，这将在.NET 4.0及以上版本中运行，如果我的版本低于此，则可能需要一个简单的扩展方法。 - Tigran

@Tigran，OrderBy和First LINQ方法自.Net 3.5以来就已经可用。但是我理解你的意思，回答已更新。 - Rich O'Kelly

+1，但是我使用的是3.5版本，没有那个功能。因此最好有一些“B”选项。 - Tigran

如果你有一个数组 {5,7,8,15,20} 和 targetNumber = 6，最接近的数将是 5；如果数组是 {7,5,8,15,20}，最接近的数将是 7。 - JanOlMajti

@Tigran：你缺少哪个函数？如果你正在使用.NET 3.5，那么你肯定有OrderBy和First - 尽管你需要一个System.Linq的using指令。 - Jon Skeet

Answer 3

Jon和Rich都给出了关于MinBy和ClosestTo的好回答。但是如果你的目的是查找单个元素，我绝不建议使用OrderBy，因为对于这种任务来说它效率太低了。它只是一个错误的工具。

这里有一种技术，比MinBy略微更好，已经包含在.NET Framework中，但不如MinBy优雅：Aggregate

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

正如我所说的，并不像Jon的方法那样优雅，但可行。

在我的计算机上性能为：

1. 使用foreach循环 = 最快
2. Aggregate聚合函数 = 比循环慢2.5倍
3. MinBy函数 = 比循环慢3.5倍
4. OrderBy排序函数 = 比循环慢12倍

- Lee Grissom

Answer 4

数年前，我在Math.NET Numerics https://numerics.mathdotnet.com/ 中发现了一种非常优秀的方法，它与数组中的BinarySearch配合使用。这对于插值的准备工作非常有帮助，并且可以在 .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);
}

- NilesDavis

---

请注意，这并不完全回答问题。如果将此用于原始提问者的值，并提供t = 13，实际上会返回索引2，因此返回值为8而不是期望的15。 - Knelis

你是对的，这就是“LeftSegment”的意思。当然，在此之后，你必须检查左右两个候选者的距离。感谢您的纠正。 - NilesDavis

Answer 5

如果您需要找到最接近平均值的数

非常开放式风格

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;
    }
}

- Samuel Lehikoinen

---

这个回答如何解决问题？ - LuminousNutria

Answer 6

就性能而言，自定义代码会更有用。

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;
}

- Amit Srivastava