如何找到最接近任意（非成员）数字的数组元素？

Question

看似相似的问题：“在Java中找到最接近的数字”和“找到最接近的双精度数组元素”（实际上是一个地理问题）。

我有一个（排序后的）双精度数组。给定任意数字（可能与数组元素中的某个数字完全匹配，也可能不匹配），如何返回最接近匹配的数字的索引？

例如，使用以下数组：

• 1.8
• 2.4
• 2.7
• 3.1
• 4.5

查询2.5将返回索引1，对应于值2.4。

如果您想尝试此问题的一部分，请检测完全超出数组元素范围的值。例如，使用上面列出的数组，您的代码可以确定4.6在内，但5.9在外。如果您想尝试这个问题的一部分，具体细节由您决定。

- Tom Wright

---

可能是在数字集合中找到最接近的匹配项的重复问题。 - bzlm

Answer 1

Array.BinarySearch返回以下内容：

如果找到了指定的值，则返回其在指定数组中的索引。如果未找到该值且该值小于一个或多个数组元素，则返回负数，该负数为大于该值的第一个元素的索引的按位补码。如果未找到该值且该值大于数组中的任何元素，则返回负数，该负数为（最后一个元素的索引加1）的按位补码。

这样就可以确定目标数字是小于还是大于匹配数字，只需要检查两个索引即可。

- Mark Rushakoff

Answer 2

使用LINQ实现这个功能的一种方法如下：

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

它可能会有一些性能问题，但如果列表不是那么长，它不应该成为问题。此外，如果两个元素与目标值的距离相等，则它将返回这些元素中第一个索引。

- Øyvind Bråthen

---

@Steven - 谢谢。在方法上与您的方法非常相似 ;) - Øyvind Bråthen

@Øyvind: 并且你比我快了22秒 :'( - Steven

Answer 3

也许不是最快的解决方案，但肯定是一种令人愉悦的视觉享受：

double search;
double[] array;

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

var index = array.IndexOf(nearest);

请注意，这种算法绝对比二分查找算法慢，因为它需要处理数组中的每个元素，并且排序意味着构建这些项的哈希表。

- Steven

---

请注意，他要求的是最接近值的索引，而不是最接近值本身。 - Øyvind Bråthen

这是一个不错的方法 :) - Tom Wright

@Tom：当然，这远远达不到Mark的答案的性能特征。这就是为什么他得到了我的加一。 - Steven

Answer 4

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

- Amit Srivastava

---

请提供一些评论，对您的贡献进行一些描述。 - Radim Köhler

Answer 5

大概是这样的：

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]);

- Pieter van Ginkel