已阅读 this question及其答案,我得出的结论是这两种算法没有标准实现。不过,首先要介绍一些背景知识:
我们大多数人都熟悉 binarySearch 。这个想法是,给定一个排序数组(或Collection
,如果使用该类中的搜索工具),它会有效(以对数 - O(log2n) 时间)查找给定元素在数组/集合中的位置。我提供的特定链接包含以下文档:
[...] If the array contains multiple elements with the specified value, there is no guarantee which one will be found.
有时,我们并不关心是否找到(或未能找到)我们感兴趣的元素的第一次或最后一次出现。但是如果我们确实关心呢?
如果我们确实关心,我们可以使用二分搜索的变体,称为下限和上限。它们分别返回给定元素的第一个和最后一个1出现。
我来自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
最好是有效的?
1但这取决于惯例。在 C++
中,上限返回大于所查找元素的第一个元素。
最佳答案
这不是您想要的 TreeSet.floor()
和 TreeSet.ceiling()
吗?
或者,如果您希望排除相等性,则可以使用 higher()
和 lower()
。
关于java - Java 中的集合和/或数组是否有正确的 upperBound 和 lowerBound?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/56623268/