c# - 不精确二分搜索：给定一个值，找到元素位置的上下索引

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