我有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)。有沒有辦法使用二分搜索快速找到匹配范圍？
uj5u.com熱心網友回復：
您需要檢查所有滿足 的事件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]]
uj5u.com熱心網友回復：
二分搜索對您沒有多大幫助，因為您搜索的不是單個基于相等性的匹配，而是可以排序的一系列結果，但對快速查找匹配沒有多大幫助。
除非您要處理大量范圍元素（1000 個），否則線性（即 O(n)）程序可以正常作業。
為了加快速度，請事先按開始日期排序，這樣當您遇到開始日期在目標之后的元素時，您對串列的迭代將能夠提前退出。
uj5u.com熱心網友回復：
您應該瀏覽串列并在專案不在范圍內時停止。就復雜性而言，這是您能做的最好的事情。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/353917.html