Binary search on a sorted list of E(startTime,endTime) to find all E’s matched by a given time range (t1,t2)

I have Event objects as follows,

public class Event {
   String name;
   int startTime; // minutes since midnight, e.g 4:15am = 255
   int endTime;   // minutes since midnight, e.g.6:30am = 390
   // + getters/setters
}

They are sorted by startTime ASC,

events.sort(Comparator.comparing(Event::getStartTime));

Events can overlap in any way.

I need to obtain a List of all Events matching (incl. partially) a particular range t1,t2 (also ints for minutes since midnight).

List<Event> eventsMatching = findMatching(t1, t2); // e.g. between 200,205

I don’t want to go through the whole list and check e.getStartTime() <= t1 && e.getEndTime() >= t2. Since the list is sorted, I should be able to use Collections.binarySearch() in some way. But normally, a binary search finds the exact object you’re looking for: int position = Collections.binarySearch(events, key). Is there some way to find matching ranges quickly using a binary search?

Answer

Binary search will not help you much, because you’re not searching for a single equality-based match, but rather a range of results that can be ordered, but not in a way that’s much help to quickly finding matches.

Unless you’re dealing with a great many range elements (1000’s), a linear (ie O(n)) process would work OK.

To speed things up, sort by start date beforehand, so your iteration over the list would be able to exit early when you encounter an element whose start date is after the target.