不精確的二進制搜索：給定一個值，找到元素位置的上下限索引

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