不精确的二进制搜索:给定值,找到元素位置的上下索引

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