Поиск в List ближайшего большего и меньшего вещественного значения

Question

Подскажите, пожалуйста, как можно в List<double> (список сортированный) найти ближайшие большее и меньше вещественного значение и их индексы в списке, и учесть случай когда число есть и его нет.

Есть вот такой список:

List<double> heightList = new List<double>() {
    5.0, 10.0, 20.0, 30.0, 40.0, 60.0, 80.0, 100.0, 150.0, 200.0, 250.0, 300.0 };

Входное число:

double number = 5.5;

Правильный ответ при таком будет меньшее ближайшее 5.0 с индексом 0, большее ближайшее 10.0 с индексом 1.

Через бинарный поиск попытался вот так сделать

Answer 1

Поскольку у Вас очень много кода. Решил дать вам такой алгоритм.

Так как

Двоичный (бинарный) поиск (также известен, как метод деления пополам или дихотомия) — классический алгоритм поиска элемента в отсортированном массиве (векторе), использующий дробление массива на половины. Используется в информатике, вычислительной математике и математическом программировании.

Добавляете ваше число number, вокруг которого идет поиск в список heightList.
Сортируете heightList.
Бинарным поиском ищите своё число number. (List.BinarySearch)
Найдя индекc index, смотрите два элемента, до index - 1, index - 2 и после index + 1, index + 2итого, максимум рассматриваете 4 элемента в случае index > 1 и index < heightList.Count - 1. Иначе даже не рассматриваете индекс, который вышел за рамки списка.
Выбираете ближайший к вашему числу по модулю.

Answer 2

В библиотеке дотнета, насколько я понимаю, нет готового метода для бинарного поиска самого левого или самого правого элемента (подобно lower_bound и upper_bound в STL). Это полезно в том случае, если список может содержать много дубликатов.

Однако можно заглянуть в Вики и реализовать нужные методы на основе псевдокода:

function binary_search_leftmost(A, n, T):
    L := 0
    R := n
    while L < R:
        m := floor((L + R) / 2)
        if A[m] < T:
            L := m + 1
        else:
            R := m
    return L

function binary_search_rightmost(A, n, T):
    L := 0
    R := n
    while L < R:
        m := floor((L + R) / 2)
        if A[m] > T:
            R := m
        else:
            L := m + 1
    return R - 1

Answer 3

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

heightList.sort((a,b)=>Math.Abs(a - number) < Math.Abs(b - number) ? -1 : 1)
heightList[0] // искомая запись

БЛОГ НА HUSL

Поиск в List ближайшего большего и меньшего вещественного значения

Ответы (3 шт):