java - 使用 Collections.binarySearch() 进行谓词搜索(即不完全匹配)

Question

我有一个按升序排序的时间戳列表:

List<Instant> timestamps = ...; // note: sorted in ascending order

现在，给定输入时间戳 Instant inputTs ，我想找一个条目t在timestamps满足t.isBefore(inputTs) && inputTs.isBefore(t.plusMillis(SOME_CONSTANT)) ，即我只是在寻找 t这样inputTs位于从 t 开始的某个固定长度持续时间的范围内。我承认理论上可以有多个这样的 t s，因此允许搜索在这些之间任意选择。

Collections.binarySearch(...)重载需要一个键，表明常见/预期的用例是搜索“完全匹配”/相同的条目(抱歉，缺少更好的词)。然而，就我而言inputTs将与 timestamps 中的条目不同如inputTs预计是在某些条目之后不久的时间点t在timestamps .

我的想法是简单地制作 Comparator<Instant>我提供给Collections.binarySearch(...)当谓词成立时返回 0:

public class TimestampFinder {
    private static final long SOME_CONSTANT = 10_000;
    private List<Instant> timestamps = ... ; // initialize and sort

    public Instant find(Instant inputTs) {
        int index = Collections.binarySearch(timestamps, inputTs, (t, key) -> {
            if (t.isBefore(key) && key.isBefore(t.plusMillis(SOME_CONSTANT))) {
                // inputTs is part of the duration after t
                // return 0 to indicate that we've found a match
                return 0;
            }
            // inputTs not in interval
            // use Instant's implementation of Comparator to indicate to binarySearch if it should continue the search in the upper or lower half of the list
            return t.compareTo(key);
        });
        return index >= 0 ? timestamps.get(index) : null;
    }
} 

这是解决此问题的正确(有效)方法，还是有我忽略的更好的替代方法？注意find(Instant)的调用次数将大大超过 timestamps 中的元素数量，这就是为什么我考虑排序 timestamps 产生的开销是有保证的。

Answer 1

Collections.binarySearch 没有用于精确匹配。正如文档中所指定的，如果未找到完全匹配，它将返回 -1 - i，其中 i 是下一个较高元素的索引列表。

只需按照自然顺序搜索 inputTs 即可。如果没有找到，那么您可以从 inputTs 导出下一个更高的 Instant 的索引(只需执行 -1 - resultOfBinarySearch) 。如果该索引处的 Instant 是 before(inputTs.plusMillis(CONSTANT))，那么就完成了，否则，不存在这样的 Instant .

我确实认为您现有的解决方案以令人担忧的方式滥用了binarySearch，无论其值(value)如何。