Ghost replay - storage and timing

I am working on a car race game and just implemented a ghost sprite for replaying past races. I use a physics engine and after much reading I came to the conclusion that the best way to store the ghost data for replay would be to record the car's position and rotation at given timepoints, as for example described here: https://gamedev.stackexchange.com/a/8380/26261.

But what would be a good way to find those timepoints during replay? An example would be a record with this data:

time: +3.19932 (seconds since race start)
position:  180,40 (position at that time)
rotation: 30.4 (rotation at that time)

But I have several problems with that:

1. 
   

   When I replay, it's unlikely that I reach the exact timepoint at 3.19932 again - more likely, I will have a timepoint around 3.1 and have to find the closest matching record. When interpolating, even the closest matching above and below. This sounds very inefficient and time consuming?

   
   


2. 
   
   

   In which list structure could I store these records for a later replay? An array? Doesn't that mean that search time for records matching a certain time will increase the longer the race is?

   
   


3. 
   

   Which frequency should I use for timepoints? Each frame would be -I guess- overkill, rather I should save i.e. every nth frame and interpolate in between, which makes the storage questions in 2. even more difficult.

   
   

So is this idea even the right approach? If yes, how could I efficiently store and retrieve the data? Please note that I generally would like to go with using the data structure above, not deterministic gamestates and recording user input etc.

Thanks for any help!

EDIT: I realise I should describe the environment I use: Cocos2D for iPhone. There is a method update:(ccTime)delta. Ideally, this method would be called every 1/60 seconds, but there is no guarantee - delta is the actual time passed since the last gametick and could be a lot more or less than 1/60. It is in this method where I would like to store the current gamestate.

Answer

Doesn't that mean that search time for records matching a certain time will increase the longer the race is?

Nope :)

Say you store it as an array (note the snapshots are in chronological order, but not evenly spaced):

snapshots = [
    {time: 0.0, position: {x,y,z}},
    {time: 0.41,    position: {x,y,z}},
    {time: 0.57,    position: {x,y,z}},
    {time: 1.10,    position: {x,y,z}},

    {time: 1.67,    position: {x,y,z}},
    {time: 2.05,    position: {x,y,z}},
    {time: 3.24,    position: {x,y,z}},
    {time: 3.86,    position: {x,y,z}},
    {time: 3.91,    position: {x,y,z}},
    {time: 5.42,    position: {x,y,z}},
    ...]

Then, when the replay/game starts, you get the first and second element from the array:

nextIdx = 1

previousSnapshot = snapshots[nextIdx-1]
nextSnapshot = snapshots[nextIdx]

Then in each frame (currentTime is the current time in this new game):

if currentTime > nextSnapshot.time
    nextIdx++
    previousSnapshot = snapshots[nextIdx-1]
    nextSnapshot = snapshots[nextIdx]

# Do your magic here, e.g.:

snapshotPairGap = nextSnapshot.time - previousSnapshot.time
ratio = (currentTime - previousSnapshot.time) / snapshotPairGap
ghostPosition = {
    x: previousSnapshot.position.x + ratio*(nextSnapshot.position.x - previousSnapshot.position.x)
    y: previousSnapshot.position.y + ratio*(nextSnapshot.position.y - previousSnapshot.position.y)
    z: previousSnapshot.position.z + ratio*(nextSnapshot.position.z - previousSnapshot.position.z)
}

Of course this could be optimized by caching some of the calculations. There's no searching through the array, just looking up specific indices.