如何基于二分查找在有序Event列表中快速匹配指定时间范围的事件

核心逻辑梳理 #

两个时间区间存在交集（含端点重合，即你说的部分匹配）的充要条件为：
event.getStartTime() <= t2 && event.getEndTime() >= t1
由于你的Event列表已经按startTime升序排序，所有startTime > t2的事件必然不满足上述条件，可以通过二分查找直接排除这部分数据，大幅缩小需要遍历的范围。

实现步骤 #

• 参数校验：如果查询的t1大于t2，或者事件列表为空，直接返回空结果。
• 构造虚拟的Event作为二分查找的key，将其startTime设置为t2，使用和排序时相同的startTime比较器调用Collections.binarySearch。
• 计算右边界：
  • 如果二分查找返回非负索引，说明存在startTime等于t2的事件，向后遍历找到最后一个startTime<=t2的索引作为右边界。
  • 如果二分查找返回负索引，计算插入点为-pos -1，右边界即为插入点前一位。
  • 若右边界小于0，说明没有符合条件的事件，直接返回空。
• 遍历从0到右边界的所有事件，筛选出endTime >= t1的事件加入结果列表。

代码实现 #

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

public List<Event> findMatching(int t1, int t2, List<Event> events) {
    List<Event> result = new ArrayList<>();
    // 无效参数直接返回空
    if (t1 > t2 || events == null || events.isEmpty()) {
        return result;
    }

    // 构造仅用于startTime比较的虚拟key
    Event searchKey = new Event();
    searchKey.setStartTime(t2);
    // 用和排序一致的比较器做二分查找
    int searchPos = Collections.binarySearch(events, searchKey, Comparator.comparingInt(Event::getStartTime));

    int rightBoundary;
    if (searchPos >= 0) {
        // 找到精确匹配的startTime，定位到最后一个符合start<=t2的位置
        rightBoundary = searchPos;
        while (rightBoundary + 1 < events.size() && events.get(rightBoundary + 1).getStartTime() <= t2) {
            rightBoundary++;
        }
    } else {
        // 无精确匹配，计算插入点，右边界为插入点前一位
        int insertPos = -(searchPos + 1);
        rightBoundary = insertPos - 1;
    }

    // 右边界小于0说明没有符合start<=t2的事件
    if (rightBoundary < 0) {
        return result;
    }

    // 遍历目标区间筛选符合end>=t1的事件
    for (int i = 0; i <= rightBoundary; i++) {
        Event current = events.get(i);
        if (current.getEndTime() >= t1) {
            result.add(current);
        }
    }

    return result;
}

性能说明 #

该方案时间复杂度为O(logN + K)，其中N为事件总数量，K为满足startTime <= t2的事件数量。相比全列表遍历的O(N)，当查询的时间范围较早时性能提升非常明显。
如果你的业务场景中事件普遍时长不超过固定阈值，还可以额外优化左边界：通过二分查找找到startTime >= (t1 - 最大事件时长)的位置作为遍历起点，进一步缩小遍历范围，不过该优化不适用存在超长时间事件的场景。

内容的提问来源于stack exchange，提问作者gene b.