std :: lower_bound和std :: upper_bound的基本原理？

Question

STL提供了二进制搜索函数std :: lower_bound和std :: upper_bound,但我倾向于不使用它们,因为我无法记住它们的作用,因为它们的合同对我来说似乎完全不可思议.

只是从查看名称,我猜"lower_bound"可能是"last lower bound"的缩写,
即排序列表中的最后一个元素<=给定的val(如果有的话).
同样地,我猜"upper_bound"可能是"第一个上限"的缩写,
即排序列表中的第一个元素> =给定的val(如果有的话).

但文档说他们做了一些与此截然不同的事情 - 对我来说似乎是倒退和随机的混合.要解释doc:
- lower_bound找到第一个元素> = val
- upper_bound找到第一个元素> val

所以lower_bound根本找不到下限; 它找到了第一个上限!？并且upper_bound找到第一个严格的上限.

这有意义吗？？你怎么记得的？

Answer 1

如果在[ first,last] 范围内有多个元素,其值等于val您要搜索的值,则范围为[ l,u]

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

恰好是等于val[ first,last] 范围内的元素范围.所以l并且u是相等范围的"下界"和"上界" .如果你习惯于以半开放的间隔思考,这是有道理的.

(注意std::equal_range,在一次调用中,它将返回一对中的下限和上限.)

Answer 2

std::lower_bound

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

std::upper_bound

返回指向范围[first,last]中第一个元素的迭代器,该元素大于 value.

因此,通过混合下限和上限,您可以准确地描述范围的开始位置和结束位置.

这有意义吗？？

是.

例:

想象矢量

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, " "));

打印:4 4 4

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

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

Answer 3

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

因此,如果您有多个具有该值的对象已经存在于集合中,lower_bound将为您提供一个引用它们中的第一个upper_bound的迭代器,并将给出一个迭代器,该迭代器在最后一个之后立即引用该对象.

这(除其他外)使返回的迭代器可用作hint参数insert.

因此,如果您使用这些作为提示,您插入的项目将成为具有该值的新第一个项目(如果您使用lower_bound)或具有该值的最后一个项目(如果您使用upper_bound).如果集合之前没有包含具有该值的项目,您仍将获得一个迭代器,可以将其用作hint将其插入集合中的正确位置.

当然,您也可以在没有提示的情况下插入,但是使用提示可以保证插入以恒定的复杂性完成,只要插入的新项目可以在迭代器指向的项目之前插入(就像它将在这两种情况).

Answer 4

我接受了布赖恩的回答，但我刚刚意识到另一种有用的思考方式，这增加了我的清晰度，所以我添加了这个以供参考。

将返回的迭代器视为指向，而不是指向元素 *iter，而是在该元素之前，即在该元素和列表中的前一个元素之间（如果有的话）。这么一想，两个函数的契约就变得对称了：lower_bound 找到了从 <val 到 >=val 的转换位置，upper_bound 找到了从 <=val 到 >val 转换的位置。或者换句话说，lower_bound 是比较等于 val 的项目范围的开始（即 std::equal_range 返回的范围），而 upper_bound 是它们的结束。

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

Answer 5

考虑一下顺序

1 2 3 4 5 6 6 6 7 8 9

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;
}