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

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

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，因此允许搜索在这些之间任意选择。

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进行排序会产生开销的原因。

最佳答案

Collections.binarySearch不必用于完全匹配。根据文档中的指定，如果找不到完全匹配的内容，它将返回-1 - i，其中i是列表中下一个较高元素的索引。

只需使用自然顺序搜索inputTs。如果未找到，则可以从Instant导出下一个更高的inputTs的索引（只需-1 - resultOfBinarySearch即可）。如果该索引处的Instant是before(inputTs.plusMillis(CONSTANT))，则说明操作完成，否则，不存在这样的Instant。

我确实认为您现有的解决方案在价值上会滥用binarySearch。