c++ - std::vector 中的二进制搜索

Question

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

我的情况如下:

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

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

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

#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;
}  

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

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

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

Answer 1

binary_find 尽管未声明返回 void，但不返回任何内容，因此它具有未定义的行为。

固定后，假设除了已排序之外，您对 vector 的内容没有任何具体了解，二分查找几乎是最优的。

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