CODEWITHSUNDEEP
javaalgorithm
gene b.
gene b.

Reputation: 12026

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?

Upvotes: 1

Views: 78

Answers (3)

Bohemian
Bohemian

Reputation: 425208

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.

Upvotes: 1

user17223316
user17223316

Reputation:

You need to check for all events that meet e.startTime <= t1.

record Event(String name, int startTime, int endTime) {}
List<Event> list = Arrays.asList(
    new Event("a", 2, 3), new Event("b", 3, 4),
    new Event("c", 0, 1), new Event("d", 4, 5));
list.sort(Comparator.comparing(Event::startTime));
System.out.println("sorted:   " + list);
int t1 = 2, t2 = 3;
List<Event> filtered = list.stream()
    .takeWhile(e -> e.startTime() <= t1)
    .peek(e -> System.out.println("checked:  " + e))
    .filter(e -> e.endTime() >= t2)
    .toList();
System.out.println("filtered: " + filtered);

output:

sorted:   [Event[name=c, startTime=0, endTime=1], Event[name=a, startTime=2, endTime=3], Event[name=b, startTime=3, endTime=4], Event[name=d, startTime=4, endTime=5]]
checked:  Event[name=c, startTime=0, endTime=1]
checked:  Event[name=a, startTime=2, endTime=3]
filtered: [Event[name=a, startTime=2, endTime=3]]

Upvotes: 4

Zinedine Benkhider
Zinedine Benkhider

Reputation: 386

You should browse the list and stop when an item is not in range. In terms of complexity, it's the best you can do.

Upvotes: 1

Related Questions