Inexact Binary Search: Given a Value, Find the Upper and Lower Index Of The Element Position

Question

I have a List<KeyValuePair<double, double>>, the list is sorted by KeyValuePair.Key, so it's amendable to binary search. And I have a double object. Now, my task is to find the index of the double object. Here are the conditions that apply:

1. If that double object matches one of the KeyValuePair.Key within a specified tolerance, then the corresponding KeyValuePair.Value should be returned.
2. If the double object falls outside the max and min range of KeyValuePair.Key, then a 0 should be returned.
3. If the double object falls within the max min of the KeyValuePair.Key, but not matched any of the KeyValuePair.Key within a specified tolerance, then the get the average of the nearest upper and nearest lower KeyValuePair.Value ( as measured by KeyValuePair.Key).

I know that a binary search implementation is available in C#, but it is not exactly suited to my needs. I would like to ask is there any implementation out there that already meets my needs? I don't want to spend a few hours writing and debugging the code that other people has already written, debugged and perfected.

Answer 1

This can be done fairly easily with a comparer 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);
     }
 }