CODEWITHSUNDEEP
javascriptarrays
Andre M
Andre M

Reputation: 7534

Finding array entry closest to required value, in Javascript?

I have an array of objects, each with a property 'time'. The array is already sorted by time. I now want to find the entry idx, such that:

  findIdx(time): return idx where idx <= time < idx+1

While I can loop through the entries and return as soon as I have found a corresponding entry, I am concerned this will be very heavy in the use case I have. The use case is scrubbing though a video, so the list would likely be looped through frequently during that action.

My current thought is to create a tree of increasingly precise times, such that I would reduce the looping through the list, by only querying the appropriate ranges.

I may be overthinking the problem, but any insight would be appreciated.

Upvotes: 0

Views: 60

Answers (1)

Draco18s no longer trusts SE
Draco18s no longer trusts SE

Reputation: 15941

As I said in a comment, if the array is sorted, you can use a binary search to lower the CPU cost.

A second advantage to a binary search algorithm is that if the value is not contained in the array, you also know what index it would be at, making insertion (and maintaining the sorted nature of the array) easy.

Upvotes: 1

Related Questions