c++ - std 库中有什么函数可以对向量进行二进制搜索并找到一个元素？

Question

我有一个节点结构

struct Node{CString text, int id;};

在一个排序的向量中。

我想知道算法中是否有一个函数可以对向量进行二进制搜索并找到一个元素。

Answer 1

std::binary_search()将告诉您容器中是否存在值。

std::lower_bound()/std::upper_bound()将迭代器返回到值的第一次/最后一次出现。

您的对象需要实现operator<这些算法才能工作。

Answer 2

是的，有一个名为“binary_search”的函数 std::binary_search

你先给它，最后给它一个值或一个谓词。

请参阅此处获取示例

将它与Martin York 的operator== 结合起来，你应该没问题（或者你可以编写一个谓词函子

Answer 3

而不是排序的 vector<Node>
为什么不使用地图。这是一个分类容器。因此，通过 std::find() 对此进行的任何搜索都会自动具有与二进制搜索相同的属性。

Answer 4

用于std::equal_range查找已排序向量中的一系列元素。 std::equal_range返回一个std::pair迭代器，为您提供与您提供的参数相等的元素向量范围。如果范围为空，则您的项目不在向量中，范围的长度告诉您项目在向量中出现的次数。

这是一个使用 ints 而不是 的示例struct Node：

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>

int main(int argc, const char * argv[])
{
    std::vector<int> sorted = { 1, 2, 2, 5, 10 };

    auto range = std::equal_range(sorted.begin(), sorted.end(), 20);
    // Outputs "5 5"
    std::cout << std::distance(sorted.begin(), range.first) << ' '
              << std::distance(sorted.begin(), range.second) << '\n';

    range = std::equal_range(sorted.begin(), sorted.end(), 5);
    // Outputs "3 4"
    std::cout << std::distance(sorted.begin(), range.first) << ' '
              << std::distance(sorted.begin(), range.second) << '\n';

    range = std::equal_range(sorted.begin(), sorted.end(), -1);
    // Outputs "0 0"
    std::cout << std::distance(sorted.begin(), range.first) << ' '
              << std::distance(sorted.begin(), range.second) << '\n';

    return 0;
}

要使这项工作与struct Node您一起工作，您必须提供一个operator < forstruct Node或将比较器传递给std::equal_range. 您可以通过提供 lambda 作为参数std::equal_range来比较您的结构来做到这一点。

std::vector<Node> nodes = { Node{"hello", 5}, Node{"goodbye", 6} };
Node searchForMe { "goodbye", 6 };
auto range = std::equal_range(nodes.begin(), nodes.end(), searchForMe,
                               [](Node lhs, Node rhs) { return lhs.id < rhs.id; });