不精确的二进制搜索：给定一个值，找到元素位置的上下限索引

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