std::vector 中的二进制搜索

Question

我正在尝试寻找向量元素在另一个向量中的位置。在这里，我有兴趣使用与 binary search 一样快的实现。我有不同的长度为 100 万或更长的向量，所以我正在努力实现更快的目标。

我的情况如下：

1) vector 我正在搜索的排序。

2) 我正在搜索的元素将始终存在，即我没有 not found 的情况，我想获取索引以更快的方式处理矢量元素。

我尝试了以下代码来获取向量元素的索引。

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

template<class Iter, class T>
Iter binary_find(Iter begin, Iter end, T val)
{
    Iter i = std::lower_bound(begin, end, val);
    return i;
}

int main() {
    std::vector<std::string> values = {"AAAAAA","AB", "AD" ,"BCD","CD", "DD" };
    std::vector<std::string> tests = {"AB", "CD","AD", "DD"};
    for(int i=0 ; i < tests.size(); i++) {
        int pos = binary_find(values.begin(), values.end(), tests.at(i))- values.begin();
    std::cout << tests.at(i) << " found at: " << pos <<std::endl;
    }
    return 0;
}

我想知道代码是否与二进制搜索实现匹配。??

有没有更快的获取向量元素索引的方法？

任何改进此代码的进一步建议。

Answer 1

Q1：我想知道代码是否与二进制搜索实现相匹配？？

是，它（almost) is. Check std::lower_bound，它指出：

Complexity:

On average, logarithmic in the distance between first and last: Performs approximately log2(N)+1 element comparisons (where N is this distance). On non-random-access iterators, the iterator advances produce themselves an additional linear complexity in N on average.

Q2：有没有更快的获取向量元素索引的方法？？

这是一个相当宽泛的问题。

问题 3：任何改进此代码的进一步建议。

世界您好，Code Review！

PS - 你编译代码了吗？它给出了几个消息，例如：

warning: no return statement in function returning non-void [-Wreturn-type]

启用警告编译，如下所示：

g++ -Wall main.cpp

Answer 2

~~binary_find 没有 return 任何东西，尽管没有向 return void 声明，所以它有未定义的行为。~~

~~固定后，~~假设您对向量的内容除了排序之外没有其他具体知识，二分查找几乎是最优的。

但是，对于基于谓词的查找，还有其他数据结构比向量更快。如果性能至关重要，您应该查看搜索树和哈希映射。由于您的键是字符串，因此尝试和有向无环词图可能特别有效。您可能想要衡量哪种最适合您的用例。

Answer 3

http://www.cpluplus.com says that the behavior of binary_search 等同于：

template <class ForwardIterator, class T>
bool binary_search (ForwardIterator first, ForwardIterator last, const T& val) {
    first = std::lower_bound(first, last, val);
    return (first != last && !(val < *first));
}

所以是的，lower_bound 是您的首选武器。但是当你取差时你应该使用distance。因为，如果有更快的方法来获取位置，它将被滚动到该函数中。

就其他改进而言，我建议使用 C++14 的 begin and end 而不是调用仅用于包装 lower_bound 的函数（并且无法正确 return 一个值。）所以我写这段代码的方式看起来像：

auto pos = distance(lower_bound(begin(values), end(values), tests[i]), begin(values));

std::vector 中的二进制搜索

Binary search in std::vector

c++

vector

std

binary-search