Optimal Javascript algorithm for finding time-based events

Question

I have an array of objects in Javascript, which contain an event start and end moment as milliseconds. Our codebase currently uses a naive search algorithm that iterates through the array until we find an event that contains a moment in time:

// time contains the moment of time we're looking to find an event for

profile.tempbasaltreatments.forEach( function eachTreatment (t) {
    if (time <= t.endmills && time >= t.mills) {
      return t;
    }
});

which doesn't cut it with the performance with larger datasets. What'd be a good algorithm / data model to efficiently go through the object array to find an event that encapsulates a moment in time? You can assume that in case the events overlap, first match is always sufficient.

Answer 1

I would suggest these pre-processing steps (before searching):

1. Optionally take a copy of the original array, if needed for other purposes;
2. Sort the array by event start times. If possible, this should really be done by the database, which can maintain an index for that.
3. Remove events from the array that have an end time that comes before the previous event's end time. When a time would match with this removed event, it can also match with the previous event. Since matching any event is good enough, we can remove this event.

Then the search would be binary, as follows:

1. Set range of search to the whole array. A range is expressed as a start and end index in the array (not as two times)
2. Take the middle element of that range
3. If this event matches the given time, exit with success
4. If this event has a start time greater than the given time, repeat from step 2 with the half of the range that comes after the selected element
5. Otherwise take the other half of the range (before the selected element) and repeat from 2
6. Stop repeating if the range has no more events and exit with failure.

The pre-processing should be done only once, which has time complexity O(n log n) if you still need to sort, otherwise it is O(n). Once that is done you can repeatedly find events in O(log n) time.

Here is some JavaScript code for the above:

// Create a copy of the original array and sort it by event start date
var events = profile.tempbasaltreatments.slice(0).sort(function (a, b) { 
    return a.mills - b.mills;
});

// Remove events that fall completely within the limits of another event.
// They are not needed to find an event for a given time.
for (var i = 0; i < events.length-1;) {
    if (i && events[i].endmills < events[i-1].endmills) {
         events.splice(i, 1);
    } else {
         i++;
    };
}
// Now also the remaining events' end dates are sorted

// function for fast search in events:    
function findEvent(events, time) {
    // Binary search for event
    var first = 0, last = events.length - 1;
    while (first <= last) { 
        var i = first + Math.floor((last - first) / 2);
        var t = events[i];
        if (time >= t.mills && time <= t.endmills) return t;
        if (time < t.mills) {
            last = i - 1;
        } else { // time > t.endmills
            first = i + 1;
        }
    }
    // returns undefined
}

// Example call: find a currently running event:
var foundEvent = findEvent(events, new Date().getTime());

Addendum

Here is how the filtering happens in the last pre-processing step. First a timeline of how events are ordered after sorting on start time:

a: ---------------
b:     -------
c:      ------------------
d:         --
e:            --  
f:                -----

The events that can be eliminated are b:

a: ---------------
c:      ------------------
d:         --
e:            --  
f:                -----

....then d:

a: ---------------
c:      ------------------
e:            --  
f:                -----

...then e:

a: ---------------
c:      ------------------
f:                -----

... and f:

a: ---------------
c:      ------------------

It is clear that the total covered period is the same as in the original, before the filtering.

Answer 2

If the events are sorted by start time, "mid time" or end time, you could use a binary search to find one close by, then do a local linear search to find one that includes the time stamp (the local search direction depends on the sort order: If the events are ordered by start time, you need to look in the direction of decreasing start time, starting at the closest start time).

The main problem with this approach is that it's slow when there is no maximum event duration, as this means that there is no stop criterion for the local search other than reaching the end of the list.

A better approach might be to store the events in a data structure suitable for efficient access, e.g. an interval tree.