Here's an example of an interpolated search... there might be easier ways,
but it appears to work very well if the data is approximately linear (i.e.
the keys are coming in at a fairly regular spacing - they don't have to be
exactly spaced).

Note that it doesn't recurse - it takes a stab using interpolation and then
walks the rest of the way from there. My reasoning is: if the first guess is
fairly close, then we haven't got far to go anyway; if the first guess is
wrong, then it means that the list is wildly non-linear, so there is no
reason to suspect that another interpolation will be any better - may as
well just treck...

You wouldn't keep the [On]Performance event/method in production code - this
is just to prove that it hasn't had to walk very far, even for long lists.
With neatly spaced data like above, I get "1" for a value that is an exact
match (i.e. we jumped to the item on our first guess) and "2" otherwise
(meaning it had to check a second value). Not bad.

using System;
using System.Collections.Generic;

static class Program
{
   static void Main()
   {
       LinearList<DateTime, Foo> list = new LinearList<DateTime,
Foo>(Interpolate);
       list.Performance += new
EventHandler<CounterEventArgs>(list_Performance);
       // lots of sample data...
       // note that it is *roughly* linear (doesn't have to be exact)
       Random rand = new Random(987654);
       DateTime lookForThis = DateTime.MaxValue;
       for (int days = -350; days < 350; days++)
       {
           DateTime key = DateTime.Today.AddDays(days).
                   AddMinutes(rand.Next(-600, 600));
           if (days == 100)
           {
               lookForThis = key;
           }
           list.Add(key, new Foo { A = days });
       }
       Foo foo1 = list.FindNearestValue(DateTime.Today.AddHours(-6)),
           foo2 = list.FindNearestValue(DateTime.Today.AddHours(6)),
           foo3 = list.FindNearestValue(DateTime.Today.AddHours(18)),
           foo4 = list.FindNearestValue(lookForThis);
   }

   static void list_Performance(object sender, CounterEventArgs e)
   {
       Console.WriteLine("OpCount: {0}", e.Counter);
   }

   public static double Interpolate(DateTime min, DateTime value, DateTime
max)
   {
       long minTicks = min.Ticks,
           range = max.Ticks - minTicks;
       double offset = value.Ticks - minTicks;

       return range == 0 ? 0 : offset / range;
   }
}
class Foo
{

   public int A { get; set; }
   public int B { get; set; }
   private readonly Bar c = new Bar();
   public Bar C { get { return c; } }
}
class Bar
{
   public int X { get; set; }
   public int Y { get; set; }
}
public class LinearList<TKey, TValue> : SortedList<TKey, TValue>
{
   private readonly Func<TKey, TKey, TKey, double> interpolation;
   public LinearList(Func<TKey, TKey, TKey, double> interpolation) :
this(interpolation, null) { }
   public LinearList(Func<TKey, TKey, TKey, double> interpolation,
IComparer<TKey> comparer)
       : base(comparer ?? Comparer<TKey>.Default)
   {
       if (interpolation == null) throw new
ArgumentNullException("interpolation");
       this.interpolation = interpolation;
   }

   private int ThisOrNext(int index, TKey value)
   {
       TKey left = Keys[index];
       if (Comparer.Compare(value, left) <= 0) return index;
       TKey right = Keys[index + 1];
       if (Comparer.Compare(value, right) >= 0) return index + 1;
       double factor = interpolation(left, value, right);
       if (factor < 0 || factor > 1)
       {
           throw new InvalidOperationException("Interpolation expected in
interval [0,1] since value is in range");
       }
       return factor <= 0.5 ? index : index + 1;
   }
   public TValue FindNearestValue(TKey key)
   {
       int index = FindNearestIndex(key);
       return index < 0 ? default(TValue) : this.Values[index];
   }
   public int FindNearestIndex(TKey key)
   {
       int count = Count, opCount = 1;
       try
       {
           switch (count)
           { // trivial cases
               case 0: return -1;
               case 1: return 0;
               case 2: return ThisOrNext(0, key);
           }
           TKey lowerBound = this.Keys[0], upperBound = this.Keys[count -
1];
           IComparer<TKey> comparer = Comparer;
           // check if it goes outside [or is on boundary of] our range
(return min/max)
           if (comparer.Compare(key, lowerBound) <= 0) return 0;
           if (comparer.Compare(key, upperBound) >= 0) return count - 1;

           double factor = interpolation(lowerBound, key, upperBound);

           int testIndex = (int)Math.Round((count - 1) * factor),
               compare = comparer.Compare(key, this.Keys[testIndex]);
           if (compare == 0)
           {
               return testIndex; // hit!
           }
           else if (compare < 0)
           {
               // we guessed too high... look lower
               for (int i = testIndex - 1; i >= 0; i--)
               {
                   opCount++;
                   compare = comparer.Compare(key, this.Keys[i]);
                   if (compare == 0) return i; // hit!
                   if (compare > 0)
                   {
                       return ThisOrNext(i, key);
                   }
               }
               return ThisOrNext(0, key);
           }
           else // compare > 0
           {
               // we guessed too low... look higher
               for (int i = testIndex + 1; i < count - 1; i++)
               {
                   opCount++;
                   compare = comparer.Compare(key, this.Keys[i]);
                   if (compare == 0) return i; // hit!
                   if (compare < 0)
                   {
                       return ThisOrNext(i - 1, key);
                   }
               }
               return ThisOrNext(count - 2, key);
           }
       }
       catch
       {
           opCount = 0;
           throw;
       }
       finally
       {
           if (opCount > 0) OnPerformance(opCount);
       }
   }
   // give an indication of how good/bad our search was...
   public event EventHandler<CounterEventArgs> Performance;
   protected virtual void OnPerformance(int opCount) {
       if (Performance != null) Performance(this, new
CounterEventArgs(opCount));
   }
}
public sealed class CounterEventArgs : EventArgs {
   private readonly int counter;
   public int Counter {get {return counter;}}
   public CounterEventArgs(int counter) {
       this.counter = counter;
   }
}

Yes, A/B/C are timestamped seperately, ie each A,b and C have their
individul timestamps. I generally need to search every 5-10sec. The
data is also generally coming in at a regular interval of once very
second. Beyond how many values is it better to read and write from a
file? Is it possible to read upto a certain number from memory and if
older values are required, read from a file, ie assuming I keep saving
the older values from memory to file?
Thanks.