c++ - rationale for std::lower_bound and std::upper_bound?

Question

STL provides binary search functions std::lower_bound and std::upper_bound, but I tend not to use them because I've been unable to remember what they do, because their contracts seem completely mystifying to me.

Just from looking at the names, I'd guess that "lower_bound" might be short for "last lower bound",
i.e. the last element in the sorted list that is <= the given val (if any).
And similarly I'd guess "upper_bound" might be short for "first upper bound",
i.e. the first element in the sorted list that is >= the given val (if any).

But the documentation says they do something rather different from that-- something that seems to be a mixture of backwards and random, to me. To paraphrase the doc:
- lower_bound finds the first element that's >= val
- upper_bound finds the first element that's > val

So lower_bound doesn't find a lower bound at all; it finds the first upper bound!? And upper_bound finds the first strict upper bound.

Does this make any sense?? How do you remember it?

score 92 · Accepted Answer

如果范围 [ 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将在一次调用中返回一对中的下限和上限。）

score 32 · Accepted Answer

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

score 14 · Accepted Answer

在这种情况下，我认为一张图片值一千字。假设我们使用它们2在以下集合中进行搜索。箭头显示了两者将返回的迭代器：

在此处输入图像描述

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

hint这（除其他外）使返回的迭代器可用作insert.

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

当然，您也可以在没有提示的情况下插入，但是使用提示可以保证插入以恒定的复杂性完成，前提是可以在迭代器指向的项目之前立即插入要插入的新项目（因为它将在这两种情况）。

score 7 · Accepted Answer

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

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

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

score 6 · Accepted Answer

考虑序列

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

score 2 · Accepted Answer

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

lower_bound：查找可以在不更改顺序的情况下插入 [val]的第一个位置。

upper_bound：查找可以在不更改顺序的情况下插入[ val] 的最后一个位置。

this [first, last) 形成一个范围，可以插入 val 但仍保持容器的原始顺序

lower_bound return "first" 即找到"范围的下边界"

upper_bound return "last" 即找到"范围的上边界"

score 1 · Accepted Answer

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

如果您试图在序列中查找某些内容，请使用lower_bound- 如果找到，它将直接指向该元素。

如果要插入序列，请使用upper_bound- 它保留重复项的原始顺序。

score 0 · Accepted Answer

是的。这个问题绝对有道理。当有人给这些函数起名字时，他们只考虑具有重复元素的排序数组。如果您有一个具有唯一元素的数组，“std::lower_bound()”的行为更像是搜索“上限”，除非它找到实际元素。

所以这就是我对这些功能的记忆：

如果您正在执行二进制搜索，请考虑使用 std::lower_bound()，并阅读手册。std::binary_search() 也是基于它的。
如果您想在唯一值的排序数组中找到值的“位置”，请考虑 std::lower_bound() 并阅读手册。
如果您有在排序数组中搜索的任意任务，请阅读 std::lower_bound() 和 std::upper_bound() 的手册。

自从您上次使用这些功能后一两个月后未能阅读手册，几乎肯定会导致错误。

score 0 · Accepted Answer

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

score -1 · Accepted Answer

对于数组或向量：

std::lower_bound：返回一个迭代器，指向范围内的第一个元素

小于或等于值。（对于数组或向量按降序排列）
大于或等于值。（对于数组或向量按递增顺序）

std::upper_bound：返回一个迭代器，指向范围内的第一个元素

小于值。（对于数组或向量按降序排列）
大于值。（对于数组或向量按递增顺序）

c++ - rationale for std::lower_bound and std::upper_bound?

10 回答 10

Related

Reference