java - Java 中的集合和/或数组是否有正确的 upperBound 和 lowerBound？

Question

已阅读 this question及其答案，我得出的结论是这两种算法没有标准实现。不过，首先要介绍一些背景知识:

我们大多数人都熟悉 binarySearch 。这个想法是，给定一个排序数组(或Collection，如果使用该类中的搜索工具)，它会有效(以对数 - O(log₂n) 时间)查找给定元素在数组/集合中的位置。我提供的特定链接包含以下文档:

[...] If the array contains multiple elements with the specified value, there is no guarantee which one will be found.

有时，我们并不关心是否找到(或未能找到)我们感兴趣的元素的第一次或最后一次出现。但是如果我们确实关心呢？

如果我们确实关心，我们可以使用二分搜索的变体，称为下限和上限。它们分别返回给定元素的第一个和最后一个¹出现。

我来自C++背景，我真的很喜欢我可以使用std::lower_bound和std::upper_bound(并且维护排序的容器的成员函数版本，例如容器上的 std::map 或 std::set)。

最简单的用例是，给定一个已排序的集合，确定有多少个元素等于某个 x 。 This answer我最初链接的问题包含以下内容:

[After performing a binarySearch] Then you continue iterating linearly until you hit to the end of the equal range.

问题是这个操作是线性的，对于具有随机访问的集合，我们可以做得更好 - 我们可以使用下限和上限，然后减去返回的索引，我们得到对数结果，而不是线性，时间。

本质上，令我惊讶的是 Java 中不可能实现上限和下限算法。我知道我自己可以轻松实现它们，但是，例如，如果我的数据存储在 TreeMap 或 TreeSet 中怎么办？它们不是随机访问的，但考虑到它们的实现，上限和下限可以很容易地实现为它们的方法。

最后，我的问题是 - Java 中是否有上限和/或下限的实现，对于 TreeSet 和 TreeMap 最好是有效的？

<小时/>

¹但这取决于惯例。在 C++ 中，上限返回大于所查找元素的第一个元素。

Answer 1

这不是您想要的 TreeSet.floor() 和 TreeSet.ceiling() 吗？

或者，如果您希望排除相等性，则可以使用 higher() 和 lower()。