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's 运算符 == 你应该没问题（或者你可以写一个谓词函子

Answer 3

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

Answer 4

使用 std::equal_range 查找排序向量中的元素范围。 std::equal_range 返回一个 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;
}

要使其与 struct Node 一起工作，您必须提供一个运算符 用于struct 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; });