C++有效地找到向量中第一个最接近的匹配值？

Question

鉴于未排序的矢量{6.0,3.02,4.2,5.3}以及给定的0.1的阈值,我怎样才能有效地找到C++中的给定阈值内的所述第一匹配的值3(例如)？我目前的实现如下,但它的复杂度为O(n).如果可能的话,我想将其改进为O(log n).非常感谢提前

std::vector<double> array = {6.0, 3.02, 4.2, 5.3};  
double val = 3 // the to be found value within the array above
double thresh = 0.1; // max threshold of the matching value
double found; // the matching value
for (int i = 0; i < array.size(); i++){
    if ( abs(array[i] - val) < thresh){
        found = array[i];
    }
}

输出应为3.02,因为它是允许阈值0.1内给定数组中与3的第一个最接近的匹配

编辑:如果我能负担得起预先对矢量进行排序,我如何重新实现上述搜索为O(log n)？谢谢

Answer 1

你正在进行线性搜索,这绝对是O(n).然而,遗憾的是,这是未排序数组/向量的最快搜索算法.

因此,为了更快地获得某些东西,您需要首先对矢量进行排序.事先做一次,或者你的结果代码实际上比线性搜索慢. std::sort()相当有效 - 虽然有一些更快的排序算法,如果你想找到一个.确保您实际存储已排序的矢量,或者根据您的需要存储到新变量中.您不希望不止一次对数据进行排序.

然后,您可以使用二进制搜索算法来定位该值.std::lower_bound或者std::upper_bound可能适合您的需求(感谢Eric提供的说明).否则,如果您使用的是标准的二进制搜索,即使完全匹配没有找到,它会让你在你正在寻找在两个或三个值,其中一个肯定是你的对手的球场.

现在,正如Eric在评论中指出的那样,排序确实比线性搜索花费更多,因此如果您只搜索该数据集一次,那么您已经拥有了最有效的方法.

编辑:在评论中,OP描述了有时需要向矢量添加新数据.这是一个要解决的相当简单的问题:只需使用二进制搜索来查找新值在排序向量中的位置,然后将其插入到那里.