查询 std::binary_search()

Question

我目前正在考虑使用 std::binary_search()（来自库）来确定列表中是否存在某个实例。在开始使用之前，我想知道它是如何工作的。

我的理解是它使用比较（对于用户定义的 structs/classes 它需要访问用户定义的比较函数）来查明对象的实例是否存在于 list/vector.根据这个网站（http://www.cplusplus.com/reference/algorithm/binary_search/），使用的范围是：

[first, last)

所以它不是 including last 因为它必须将 last 与 最后 + 1?

此外，用户定义的比较函数的逻辑并不重要，只要它区分 object/class 中的属性即可。对吗？

例如，如果我的 struct/class 包含以下内容：

coord
{
    int X;
    int Y;
}

我必须确保我的比较函数区分（以某种方式，例如 greater-than/less-than 比较）list/vector 中元素 a 和 b 的 X 和 Y 属性。

Answer 1

范围不包括 last 元素作为通用库约定，这意味着 之间的距离first 和 last 迭代器等于范围内的元素数，并且可以使用以下循环测试范围：

while(first != last)
{
    // process stuff
    ++first;
}

必须对使用相同（可能是用户定义）比较排序的已排序数据执行std::binary_search功能。

该函数需要在两个元素之间建立小于的关系。

struct coord
{
    int x;
    int y;
};

struct CoordComparator
{
    bool operator()(const coord& lhs, const coord& rhs) const
    {
        return lhs.x == rhs.x ? lhs.y < rhs.y : lhs.x < rhs.x;
    }
};

std::vector<coord> v { {1, 1}, {2, 1}, {2, 2}, {1, 2} };

std::sort(v.begin(), v.end(), CoordComparator());

if(std::binary_search(v.begin(), v.end(), coord{2, 1}, CoordComparator()))
{
    // element found in range
}

可以定义小于关系，这样大于的值被报告为小于较低的值给出反向排序关系。

Answer 2

std::binary_search() 被实现为一种常见的二进制搜索算法，它最多执行 log2(N)+1 次元素比较。（有关如何实现二进制搜索的更多信息，请查看此 link）

So is it not including last because it would have to compare last against last + 1?

不是，只是为了方便使用。您可以将函数调用为：

std::binary_search (v.begin(), v.end(), 42)

请注意 v.end() return 是指向序列末尾之后的元素的迭代器。因此，它不指向任何元素，因此不应在搜索中进行评估。

Also the user-defined compare function's logic does not matter as long as it differentiates between properties within the object/class. Is that correct?

它用于 binary_search() 的比较函数是为了知道您要查找的元素是在当前正在测试的元素之前还是之后。换句话说，比较函数必须能够比较两个元素和return如果第一个比第二个"lower"（必须放在第二个之前的容器中）。

对于您的 Coord 示例，您可以编写一个比较器函数，例如：

struct lessThanKey
{
    inline bool operator() (const Coord& lhs, const Coord& rhs)
    {
        return (lhs.x < rhs.x) || ((lhs.x == rhs.x) && (lhs.y < rhs.y));
    }
};

std::binary_search(v.begin(), v.end(), Coord{42, 42}, lessThanKey());

查询 std::binary_search()

Inquiry on std::binary_search()

c++

indexing

compare

list

binary-search