Inaccurate binary search: Given the value, find the superscript and superscript of an element's position

Question

I have List<KeyValuePair<double, double>>, the list is sorted byKeyValuePair.Key , so it can be modified for binary search. And I have an object double. Now my task is to find the index of the object double. Here are the conditions that apply:

• If this object doublematches one of KeyValuePair.Keythe within the specified tolerance, then the corresponding one must be returned KeyValuePair.Value.
• If the object doubleis outside the range of max and min KeyValuePair.Key, then 0 is returned.
• If the object doubleis within max min KeyValuePair.Key, but does not correspond to any of KeyValuePair.Keythe limits within the specified tolerance, then get the average value of the nearest upper and nearest lower KeyValuePair.Value(as measured KeyValuePair.Key).

I know that binary search implementation is available in C #, but it is not suitable for my needs. I would like to ask if there is some kind of implementation that already satisfies my needs? I don’t want to spend several hours writing and debugging code that other people have already written, debugged, and improved.

Answer 1

This can be done quite easily with a comparator and a small wrapper around 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);
     }
 }