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

Question

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

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

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

• 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

Что-то вроде этого:

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

Answer 5

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