代码之家 › 专栏 › 技术社区 › Tom Wright

如何找到与任意(非成员)数字最接近的数组元素?

approximate search c#

Tom Wright · 技术社区 · 14 年前

看似相似的问题:“ Finding closest number in an array (在爪哇)和“ find nearest match to array of doubles “(实际上是一个地理问题)。

我有一个(排序的)双打数组。给定一个任意的数字(可能与其中一个数组元素完全匹配,也可能不完全匹配),如何返回最匹配的数字的索引?

例如,使用以下数组:

一点八
二点四
二点七
三点一
四点五

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

用于检测完全不在数组元素范围内的值的奖励点。例如,使用上面列出的数组,您的代码可能决定4.6是in,但5.9是out。如果你想尝试这个问题的这一部分,具体细节就掌握在你的手中。

5 回复 | 直到 9 年前

Mark Rushakoff 14 年前

Array.BinarySearch ,返回:

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

因为你知道这个数字要么小于要么大于匹配项,但它只会给你留下两个要检查的索引。

Øyvind Bråthen 14 年前

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

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

它可能有一些性能问题,但是如果列表不长,就不应该造成问题。另外,如果两个元素距离目标值相等,它将返回这些元素的第一个索引。

Steven 14 年前

也许不是最快的解决方案,但肯定是令人愉快的眼糖:

double search;
double[] array;

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

var index = array.IndexOf(nearest);

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

Pieter van Ginkel 14 年前

像这样:

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

gevorg Dathan 9 年前

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