Find the fastest duration for a certain distance in a walk I apologize in advance if the wording of my problem is inappropriate for this forum. Or if another platform i more suitable for it. I'm new here and typically do not have to solve complex algorithmic problems.

I'm looking for an algorithm that is able to find a answer to the following question:

If I ran 10 km this morning, how can I find out how fast my fastest kilometer was? (=searching for duration of fastest km)

My "run" datastructure consists of a list of data records, where each entry contains the following information:


timestamp in milliseconds 
distance since start in meter


The data structure is arranged chronologically.

I already got a pretty straight forward solution to the problem, but I guess I would end up with a poor performance on this one:


start with the last entry of the list (i=size) and stop if available / remaining distance data[i] is smaller than 1km
search backwards in the list and calculate the distance delta for each entry until the delta for the distance is >= 1km OR (if we got a duration candidate from a previous iteration) the current calculated duration is already exceeding out current best.
if duration is too high start all over with i=i-1 until end condition is met
if a duration candidate is found remember this candidate decrease "i" and proceed with 1)


I really believe there must be an algorithm or better approach out there that can be applied to this question. Does anyone have an idea or can steer me in the right direction?
I suggest you use exactly your algorithm, except use binary search during your binary search.  You will want to store the events in an array rather than a linked list, to allow efficient random access into it.  The total running time will be $O(n \log n)$, where $n$ is the number of events in your data structure.  That seems quite reasonable, and this should be quite efficient in practice.