在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

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

固定好后，并且假设您除了排序之外对向量的内容没有具体了解，那么二分搜索几乎是最佳选择。

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