java二进制搜索已排序的E列表（开始时间，结束时间），以查找给定时间范围（t1，t2）匹配的所有E

Question

我有如下Event个对象

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
}

它们按startTime ASC分类

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

事件可以以任何方式重叠

我需要获得一个与特定范围t1,t2（也是午夜后分钟的整数）匹配（包括部分）的所有事件的列表

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

我不想浏览整个列表并选中e.getStartTime() <= t1 && e.getEndTime() >= t2。由于列表已排序，我应该能够以某种方式使用Collections.binarySearch()。但通常，二进制搜索会找到您要查找的确切对象：int position = Collections.binarySearch(events, key)。有没有办法使用二进制搜索快速找到匹配的范围

Answer 1

二进制搜索对您没有多大帮助，因为您搜索的不是单个基于等式的匹配，而是可以排序的范围，但对快速查找匹配没有多大帮助

除非你处理的是大量的范围元素（1000个），否则线性（即O（n））过程就可以了

为了加快速度，请提前按开始日期排序，这样当您遇到开始日期在目标日期之后的元素时，您对列表的迭代将能够提前退出

Answer 2

当一个项目不在范围内时，你应该浏览列表并停止。就复杂性而言，这是你所能做到的最好的

Answer 3

您需要检查所有符合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);

输出：

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]]