6

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

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

例如，使用以下数组：

  • 1.8
  • 2.4
  • 2.7
  • 3.1
  • 4.5

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

检测完全超出数组元素范围的值的奖励积分。例如，使用上面列出的数组，您的代码可能会确定 4.6 进入，但 5.9 退出。如果您想尝试这部分问题，具体情况掌握在您手中。

4

5 回答 5

11

Array.BinarySearch，它返回：

指定数组中指定值的索引（如果找到值）。如果未找到 value 并且 value 小于数组中的一个或多个元素，则为负数，它是大于 value 的第一个元素的索引的按位补码。如果未找到 value 并且 value 大于数组中的任何元素，则为一个负数，它是 (最后一个元素的索引加 1) 的按位补码。

现在这不会让你 100% 到达那里，因为你会知道这个数字小于或大于匹配，但它实际上只给你留下两个索引来检查。

于 2010-11-16T11:43:00.033 回答
6

使用 LINQ 执行此操作的一种方法如下：

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

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

于 2010-11-16T11:49:01.260 回答
3

也许不是最快的解决方案，但肯定令人愉悦：

double search;
double[] array;

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

var index = array.IndexOf(nearest);

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

于 2010-11-16T11:49:23.547 回答
0

像这样的东西：

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]);
于 2010-11-16T11:44:43.857 回答
0 
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;
        }
    }
}
于 2014-01-07T07:29:37.547 回答