std库中有什么函数可以对向量进行二分查找并找到元素?

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

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

您的对象需要实现 operator< 为了使这些算法工作。

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

你给它第一个、最后一个和一个值或谓词。

看见 here 样品

将其与 Martin York's operator==,你应该没问题(或者你可以写一个谓词functor

而不是排序向量<节点>
为什么不用地图。这是一个已分类的容器。因此,通过std::find()对此进行的任何搜索都会自动具有与二分查找相同的属性。

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

下面是一个使用int而不是 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;
}

要使此工作与 结构体类型 你要么必须提供 operator < 给 结构体类型 或通过比较器 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; });