Неточный бинарный поиск: по заданному значению найдите верхний и нижний индексы позиции элемента

Question

У меня есть List<KeyValuePair<double, double>>, список отсортирован по KeyValuePair.Key, поэтому его можно изменить в двоичном поиске.И у меня есть double объект.Теперь моя задача - найти индекс объекта double.Вот условия, которые применяются:

1. Если этот double объект соответствует одному из KeyValuePair.Key в пределах указанного допуска, то должен быть возвращен соответствующий KeyValuePair.Value.
2. Если объект double выходит за пределы максимального и минимального диапазона KeyValuePair.Key, то должен быть возвращен 0.
3. Если объект double попадает в максимальный минимум KeyValuePair.Key, но несоответствует любому из KeyValuePair.Key в пределах указанного допуска, а затем получить среднее значение ближайшего верхнего и ближайшего нижнего KeyValuePair.Value (как измерено KeyValuePair.Key).

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

Answer 1

Это можно сделать довольно легко с помощью компаратора и небольшой оболочки вокруг List<T>.BinarySearch:

static double Search(List<KeyValuePair<double, double>> list, double key) {
    int index = list.BinarySearch(
        new KeyValuePair<double, double>(key, 0), 
        new Comparer());

     // Case 1
     if (index >= 0)
         return list[index].Value;

     // NOTE: if the search fails, List<T>.BinarySearch returns the 
     // bitwise complement of the insertion index that would be used
     // to keep the list sorted.
     index = ~index;

     // Case 2
     if (index == 0 || index == list.Count)
        return 0;

     // Case 3
     return (list[index - 1].Value + list[index].Value) / 2;
 }

 class Comparer : IComparer<KeyValuePair<double, double>> {
     public int Compare(
         KeyValuePair<double, double> x, 
         KeyValuePair<double, double> y) 
     {
         if (Math.abs(x.Key - y.Key) < TOLERANCE)
             return 0;

         return x.Key.CompareTo(y.Key);
     }
 }