find item in collection with closest date

Question

if i have a collection of dates and values. I want to get the value that is either:

1. Associated to the date in the collection
2. if it doesn't exist, i want a linear interpolation between two points that are around the point i am looking for

ao, here is a simple example. If the collection is:

Date   Value  
1/1/2009   100  
1/1/2010   200  
1/1/2011   300  

if i am looking for 6/1/2010 i would get a value back 250. i can use any collection if one is better in solving than the other (dictionary, array, etc ..)

Answer 1

You can try SortedDictionary. Do something like that:

int FindInterpolated(DateTime needle)
{
    try
    {
        DateTime lower = haystack.First(key => haystack[key] <= needle);
        DateTime upper = haystack.Last(key => haystack[key] >= needle);
        int v1 = haystack[lower];
        int v2 = haystack[upper];
        long ticksLower = lower.Ticks;
        long ticksUpper = upper.Ticks;
        return (v1 * ticksLower + v2 * ticksUpper) / (ticksLower + ticksUpper);
    }
    catch (InvalidOperationException)
    {
        // thrown if needle is out of range
        // (not between smallest and biggest keys in the haystack)
        ...
    }
}

Answer 2

A simple sorted (on date) list would be sufficient. Just find the last date (let's call it d1) that is less or equal than the date you are looking for (let's call that one d). The next date d2 will then be past d, assuming there are no duplicate dates.

Now if value v1 corresponds to d1 and v2 corresponds to d2 then the value you are looking for is v1 + (v2 - v1) / (d2 - d1) * (d - d1).

Answer 3

You can use the List type to hold the pairs, Sort them and use List.BinarySearch.

For instance you could have something like the following:

struct Pair
{
    public Pair(DateTime t, int v)
    {
        date = t;
        value = v;
    }
    public DateTime date;
    public int value;
}

    ....

    List<Pair> pairs = new List<Pair>();


    pairs.Add(new Pair(DateTime.Now, 100));
    pairs.Add(new Pair(DateTime.Now, 200));

    ....

    // Sort using the time.
    pairs.Sort(delegate(Pair pair1, Pair pair2) {
                           return  pair1.date.CompareTo( pair2.date);
                        }
              );

    // Do binary search.
    int index = pairs.BinarySearch(new Pair(dateToSearch, 0), 
                                   delegate(Pair pair1, Pair pair2) { 
                                       return pair1.date.CompareTo(pair2.date); 
                                   });

    if (index >= 0) {
        // Found the element!
        return pairs[index].value;
    }

    // If not found, List.BinarySearch returns the complement 
    // of the index where the element should have been.
    index = ~index;

    // This date search for is larger than any
    if (index == pairs.Count) {
        //
    }

    // The date searched is smaller than any in the list.
    if (index == 0) {
    }

    // Otherwise return average of elements at index and index-1.
    return (pairs[index-1].value + pairs[index].value)/2;

Of course the code is not the best possible, but you get the idea: use List, Sort it and then do BinarySearch.

Lookup MSDN for more information.

List: http://msdn.microsoft.com/en-us/library/6sh2ey19.aspx

List.Sort: http://msdn.microsoft.com/en-us/library/3da4abas.aspx

List.BinarySearch: http://msdn.microsoft.com/en-us/library/3f90y839.aspx