下界和上界的基本原理？

STL 提供了二进制搜索函数 std: : low _ bound 和 std: : Upper _ bound, 但我一般不用它们因为我记不起来它们是干什么的, 因为他们的合同对我来说太神秘了。

光看名字, 我猜“下界”可能是“最后一个下界”的缩写,
例如，排序列表中的最后一个元素是 < = 给定的 val (如果有的话)。
同样，我猜“上界”可能是“第一个上界”的缩写,
例如，排序列表中的第一个元素是 > = 给定的 val (如果有的话)。

但是文件上说他们做了一些与此完全不同的事情 对我来说，这似乎是一个混合的倒退和随机。 套用医生的话:
- lower _ bound 找到第一个 > = val 的元素
上限找到第一个元素 > val

所以下界根本不会找到下界; 它会找到第一个 上界! ？ 并且上界找到第一个 严格的上限绑定。

这说得通吗？ 你怎么记得的？

20003 次浏览
小开 
std::lower_bound

返回一个迭代器，该迭代器指向范围[ first，last ]中不小于(即 大于或等于)值的第一个元素。

std::upper_bound

返回一个迭代器，该迭代器指向范围[ first，last ]中 更伟大 than 值的第一个元素。

因此，通过混合上下界，你能够准确地描述你的范围开始和结束的地方。

这说得通吗？

是的。

例如:

想象矢量

std::vector<int> data = { 1, 1, 2, 3, 3, 3, 3, 4, 4, 4, 5, 5, 6 };


auto lower = std::lower_bound(data.begin(), data.end(), 4);


1, 1, 2, 3, 3, 3, 3, 4, 4, 4, 5, 5, 6
// ^ lower


auto upper = std::upper_bound(data.begin(), data.end(), 4);


1, 1, 2, 3, 3, 3, 3, 4, 4, 4, 5, 5, 6
// ^ upper


std::copy(lower, upper, std::ostream_iterator<int>(std::cout, " "));

指纹: 444

Http://en.cppreference.com/w/cpp/algorithm/lower_bound

Http://en.cppreference.com/w/cpp/algorithm/upper_bound

小开

考虑一下顺序

1234566789

6的下界是前6的位置。

6的上界是7的位置。

这些位置作为公共(开始，结束)对，表示6值的运行。

例如:

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;


auto main()
-> int
{
vector<int> v = {1, 2, 3, 4, 5, 6, 6, 6, 7, 8, 9};
auto const pos1 = lower_bound( v.begin(), v.end(), 6 );
auto const pos2 = upper_bound( v.begin(), v.end(), 6 );
for( auto it = pos1; it != pos2; ++it )
{
cout << *it;
}
cout << endl;
}
小开
最佳答案

如果在范围[ first，last)中有多个元素，其值等于您正在搜索的值 val，那么范围[ l，u)在哪里

l = std::lower_bound(first, last, val)
u = std::upper_bound(first, last, val)

是在范围[ first，last]内等于 val的元素的范围。因此 l和 u是 等距离的“下界”和“上界”。如果你习惯于用半开间隔来思考问题，这是有道理的。

(请注意，std::equal_range将在一次调用中成对返回下界和上界。)

小开

在这种情况下，我认为一张图片胜过千言万语。假设我们使用它们在以下集合中搜索 2。箭头显示了两者将返回的迭代器:

enter image description here

因此，如果集合中已经存在多个具有该值的对象，lower_bound将提供一个引用其中第一个对象的迭代器，而 upper_bound将提供一个引用其中最后一个对象之后的对象的迭代器。

这使得返回的迭代器可以作为 insert的 hint参数使用。

因此，如果使用它们作为提示，则插入的项将成为具有该值的第一个新项(如果使用 lower_bound)或具有该值的最后一个项(如果使用 upper_bound)。如果集合以前没有包含具有该值的项，那么仍然会得到一个迭代器，它可以用作 hint，将其插入到集合中的正确位置。

当然，您也可以在没有提示的情况下插入，但是使用提示可以保证插入的复杂性不变，前提是要插入的新项可以立即插入到迭代器指向的项之前(在这两种情况下都会插入)。

小开

我接受了布莱恩的回答，但我刚刚意识到另一种有用的思考方式，这让我更加清晰，所以我添加了这个作为参考。

可以将返回的迭代器看作是指向元素 * iter 的，而不是指向元素 * iter，而是指向 之前 that 元素，即 中间 that 元素和列表中的前一个元素(如果有的话)。这样想来，两个函数的契约变得对称: 下界找到从 < val 到 > = val 的转换位置，上界找到从 < = val 到 > val 的转换位置。或者换句话说，下限是比较等于 val 的条目范围(即 std: : equals _ range 返回的范围)的开始，上限是它们的结束。

我希望他们在文档中这样谈论它(或者给出任何其他好的答案) ，这样就不会那么神秘了！

小开

这两个函数非常相似，因为它们将在排序序列中找到一个插入点，从而保持排序。如果序列中没有与搜索项相等的现有元素，它们将返回相同的迭代器。

如果你试图在序列中找到一些东西，使用 lower_bound-如果找到了，它将直接指向元素。

如果你插入到序列中，使用 upper_bound-它保留了重复序列的原始顺序。

小开

对于数组或向量:

下限: 返回一个迭代器，该迭代器指向范围中的第一个元素，即

  • 小于或等于数值。(数组或向量按降序排列)
  • 大于或等于值。(数组或向量的增加顺序)

上限: 返回一个迭代器，该迭代器指向范围中的第一个元素，即

  • 小于值。(数组或向量按降序排列)

  • 大于值。(数组或向量的增加顺序)

小开

是的。这个问题绝对有道理。当有人给这些函数命名时，他们想到的只是带有重复元素的排序数组。如果您有一个具有唯一元素的数组，“ std: : low _ bound ()”的作用更像是搜索“上限”，除非它找到了实际的元素。

这是我对这些函数的记忆:

  • 如果要进行二进制搜索，可以考虑使用 std: : low _ bound () ，并阅读手册. std: : inary _ search ()也是基于它的。
  • 如果希望在一个排序的唯一值数组中找到值的“位置”，请考虑 std: : low _ bound ()并阅读手册。
  • 如果您有一个在排序的数组中进行搜索的任意任务，请阅读 std: : low _ bound ()和 std: : Upper _ bound ()的手册。

自从上次使用这些函数一两个月后，如果不能阅读手册，几乎可以肯定会导致 bug。

小开

想象一下，如果您想要在 [first, last)中找到第一个等于 val的元素，您将要做什么。首先从第一个严格小于 val的元素中排除，然后从 last-1中向后排除严格大于 val的元素。然后剩下的范围是 [lower_bound, upper_bound]

小开

源代码实际上有第二个解释，我发现这对理解函数的意义很有帮助:

Low _ bound: 查找 [ val ]可以插入 而不改变顺序。所在的 第一位置

上限: 查找可以插入[ < strong > val ]的 最后位置 不改变顺序。

This [ first，last ]形成了一个范围，可以插入 val，但仍然保持容器的原始顺序

Low _ bound 返回值“ first”即查找“范围的下限”

上限返回“ last”即查找“范围的上限”


提交答案