Looking for the best datatype for a data storing problem

If i had a bunch of values that were possibly non-linear but ordered: 1, 3, 8, 12 and i added a new one, say 5 whats the best collection type (speed over anything else) that would store it between 3 and 8 and gimme the index so i can check whats directly behind that value and in front. it's an animation system, i am storing keyframes and i need to know whats ahead and behind so i can properly interpolate the values

Currently i'm using a hashtable (dicitonary) thats key is the frame number the keyframe was stored at with the value being the position that i want.

So with this method, its very useful for updating a keyframe upon making changes, but upon animating, finding the 3 and 8 if I have placed soem data in 5 has me iterating through the entire list to figure out the index of the current entry and then store the previous and iterate to the next.. (not to mention that everytime i add something to the dictionary, it needs to be sorted by key for this to work).

Just looking for some suggestions to tackle this fairly open ended problem.

To get some insight into my current structure for this animation tool:

I have a component called a timeline, which is what KeyframeProperties record into. So in a keyframeproperty you would call record() and it'd ask the timeline it's connected to if it can record into the current slot, if it can, it'll return the index at which the keyframe was recorded, and then the keyframe property stores that index into a dictionary it currently has with the current data for the animator. When you choose the play the animation, you call the timeline.play() function and it'll handle iterating through all connected properties and calling keyframeproperty.advanceframe(int frame#). This is why i need the previous and next frame, cause without know this, when the frame# is passed in, theres no way to know where the next interpolated destination for an animation should be..

Example: Passed in a 4 and the closest two keyframes in the property are at 3 and 7, the animation should set the starting location to the 3rd frames data, then interpolate to the 7th by 0.25 (1/(7-3) = 0.25)