Как найти ближайший элемент массива к произвольному (не членному) числу?

Question

На первый взгляд похожие вопросы: " Поиск ближайшего числа в массиве " (на Java) и " поиск ближайшего совпадения с массивом парных чисел " (на самом деле это проблема географии).

У меня есть (отсортированный) массив значений типа double.Учитывая произвольное число (которое может или не может быть точным соответствием для одного из элементов массива), как я могу вернуть индекс числа, которое является самым близким совпадением?

Например, используя следующий массив:

• 1,8
• 2,4
• 2,7
• 3,1
• 4,5

Запрос 2,5вернется с индексом 1, соответствующим значению 2,4.

Бонусные баллы за обнаружение значений, которые полностью находятся вне диапазона элементов массива.Например, используя указанный выше массив, ваш код может решить, что 4.6 включен, а 5.9 - нет.Если вы хотите попробовать эту часть вопроса, подробности в ваших руках.

Answer 1

Array.BinarySearch, что возвращает:

Индекс указанного значения в указанном массиве, если значение найдено.Если значение не найдено и значение меньше одного или нескольких элементов в массиве, отрицательное число является побитовым дополнением индекса первого элемента, который больше значения.Если значение не найдено и значение больше, чем любой из элементов в массиве, отрицательное число, которое является побитовым дополнением (индекс последнего элемента плюс 1).Это не даст вам 100% пути, поскольку вы будете знать, что число меньше или больше совпадения, но на самом деле у вас остается только два индекса для проверки.

Answer 2

Один из способов сделать это с помощью LINQ выглядит следующим образом:

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

У него могут быть проблемы с производительностью, но если список не такой длинный, это не должно вызывать проблем.Кроме того, если два элемента находятся на одинаковом расстоянии от целевого значения, он вернет первый из них.

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

Обратите внимание, что это будет абсолютно медленнее, чем алгоритм двоичного поиска, потому что он должен обрабатывать каждый элемент в массиве и сортироватьозначает создание хеш-таблицы из этих элементов.

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

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