问题标签 [lower-bound]

我喜欢std::algorithm尽可能在普通数组上使用。现在我有2个疑问；假设我想使用std::lower_bound如果我作为参数提供的值没有找到会发生什么？

打印 *f 时的结果是 20。

如果我使用std::find.

打印 *f 时的结果是 20。

1. 当找不到返回值时，是否总是返回值是原始参数？
2. 在性能方面表现std::lower_bound更好，std::find因为它实现了二进制搜索算法。如果数组很大，比如最多 10 个元素，std::find 性能会更好吗？在幕后 std::lower_bound 调用 std::advance 和 std::distance ..也许我也可以节省这些调用？

非常感谢

AFG

我正在尝试使用 Thrust 来检测是否可以在另一个数组中找到数组的每个元素以及在哪里（两个数组都已排序）。我遇到了矢量化搜索例程（lower_bound 和 binary_search）。

lower_bound 将为每个值返回可以插入到列表中的索引，考虑到它的排序。

我还需要知道是否找到了该值（可以使用 binary_search 完成），而不仅仅是它的位置。

是否可以在不进行两次搜索（调用 binary_search 然后调用 lower_bound）的情况下有效地实现两者？

我知道在标量情况下，如果找不到值，lower_bound 将返回指向数组末尾的指针，但这在矢量化版本中不会发生。

谢谢！

ListNode示例，取自 Scalas 主页，如下所示：

使用这个类，我们可以创建如下对象：

如我们所见，我们可以在String节点前添加一个整数值。我想，这是可行的，因为类型参数U将被自动设置为Any，当给prepend方法提供整数时（因为Int不是 的超类型String）。

当尝试使用自己的下限示例时，我会收到错误消息：

为什么Int这里的类型不会自动被视为示例Any中的类型ListNode？

更新 1：这也有效（没有明确地说 newListNode应该是 type Any）

我不知道如何lower_bound用zip_iterator.

这不会编译：

VS2010 说它“无法将参数 1 从 'int' 转换为 'const std::_Vector_iterator<_Myvec> &'”（加上其他几十个相同的错误），但它与一个不起眼的 boost::tuple 构造函数有关，而不是给定的 lambda。

我究竟做错了什么 ？

考虑对矩阵进行排序的问题n x n（即行和列按升序排列）。我想找到这个问题的下限和上限。

我发现它O(n^2 log n)只是对元素进行排序，然后将第一个n元素输出为第一行，将下一个n元素输出为第二行，依此类推。但是我想证明它也是Omega(n^2 log n)。

在尝试了较小的示例之后，我认为我应该证明，如果我可以使用小于n^2 log(n/e)比较来解决这个问题，它将违反对元素log(m!)进行排序所需的比较下限。m

关于如何证明这一点的任何想法？

考虑以下 Java 代码：

但为什么会这样呢？既然在内部，类型擦除使列表成为一个包含对象的列表，为什么不允许将对象（它们是所有类的超类，因此应该满足下限通配符）添加到列表中？

假设我有以下课程Animal,Fish和CatFish.

CatFish延伸Fish和Fish延伸Animal。

有一个名为 的泛型类MyPets，它有一个名为 的类型参数（泛型）T，它将使用上述类的对象进行参数化。

我的问题是，我如何创建一个下界方法，D该方法将采用该类的父类的任何对象CatFish。

我有一个排序的对象列表，我想找到对象的第一次出现和最后一次出现。在 C++ 中，我可以轻松地使用 std::equal_range （或者只有一个 lower_bound 和一个 upper_bound）。

例如：

在Java中，似乎没有简单的等价？我应该如何处理相等的范围

顺便说一句，我使用的是标准导入 java.util.List；

首先，我知道

1. 下限为 O(nlogn)
2. 以及如何证明

我同意下限应该是 O(nlogn)。

我不太明白的是：

对于某些特殊情况，比较次数实际上甚至可能低于下限。例如，使用冒泡排序对已排序的数组进行排序。比较次数为 O(n)。

那么如何真正理解下界的概念呢？

维基百科上的经典定义：http ://en.wikipedia.org/wiki/Upper_and_lower_bounds没有多大帮助。

我目前对此的理解是：

基于比较的排序的下限实际上是最坏情况的上限。

即，在最坏的情况下你能做到什么程度。

这个对吗？谢谢。

我需要一个内置的数据结构，C#它的功能类似于c++ 中的std::set（或std::map）。对我来说重要的是结构应该被排序（因此Dictionary不会在这里做）并且有一个类似的方法lower_bound（即返回至少具有值的第一个元素v）。我还需要从结构中插入和删除元素。如果可能的话，我需要这些操作具有复杂性O(log(n))。你能指出我合适的数据结构C#吗？