Before searching, I recommend implementing the following pre-processing steps:
- If necessary, make a copy of the original array for future reference;
- Arrange the array based on event start times. Ideally, this should be handled by the database with an index specifically for this purpose;
- Eliminate events from the array that end before the previous event's end time. Since a matching event is sufficient, any overlap can be disregarded.
Subsequently, conduct a binary search as outlined below:
- Define the search range as the entirety of the array, represented by start and end indices;
- Select the middle element within that range;
- If this event aligns with the specified time, conclude successfully;
- If the start time of this event exceeds the given time, repeat from step 2 with the latter half of the range;
- Otherwise, proceed with the first half of the range (prior to the selected element) and return to step 2;
- Termination occurs when there are no more events in the range, resulting in failure.
The pre-processing stage only needs to be executed once, with a time complexity of O(n log n) if sorting is required; otherwise, it simplifies to O(n). Subsequent event searches can then be accomplished in O(log n) time.
Below is a snippet of JavaScript code encompassing the aforementioned process:
// Make a sorted copy of the original event array
var events = profile.tempbasaltreatments.slice(0).sort(function (a, b) {
return a.mills - b.mills;
});
// Remove redundant events to streamline the search process
for (var i = 0; i < events.length-1;) {
if (i && events[i].endmills < events[i-1].endmills) {
events.splice(i, 1);
} else {
i++;
};
}
// The remaining events are also sorted by their end dates
// Function for efficiently locating events in the array:
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;
}
}
// Undefined is returned if no match is found
}
// Example usage: locate a currently ongoing event
var matchedEvent = findEvent(events, new Date().getTime());
Additional Information
This section elucidates the filtering process in the final pre-processing step. Initially, events are organized according to their start times:
a: ---------------
b: -------
c: ------------------
d: --
e: --
f: -----
The events subject to elimination are identified sequentially, starting with b:
a: ---------------
c: ------------------
d: --
e: --
f: -----
Then, d gets removed:
a: ---------------
c: ------------------
e: --
f: -----
Following that, e is excluded:
a: ---------------
c: ------------------
f: -----
Last to be removed is f:
a: ---------------
c: ------------------
Evidently, the overall coverage period remains unchanged compared to the original arrangement before filtering.