C++ 高效查找 vector 中第一个最接近的匹配值？

Question

给定未排序的 vector {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 的匹配项

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

Answer 1

您正在执行线性搜索，这绝对是 O(n)。然而，不幸的是，对于未排序的数组/vector ，这是最快的搜索算法。

因此，为了更快地获得某些东西，您需要先对 vector 进行排序。 预先做一次，否则你的结果代码实际上会比线性搜索慢。 std::sort() 相当高效——尽管有一些更快的排序算法，如果你想找到一个。根据您的需要，确保您实际存储了排序后的 vector ，可以就地存储，也可以存储在新变量中。 您不希望对数据进行多次排序。

然后，您可以使用二进制搜索算法来定位该值。 std::lower_bound 或 std::upper_bound 可能会满足您的需要(感谢 Eric 的说明)。否则，如果您使用的是标准二分搜索，即使未找到完全匹配项，它也会将您置于查看两个或三个值的大致范围内，其中一个绝对是您的匹配项。

现在，正如 Eric 在评论中指出的那样，排序的成本确实高于线性搜索，因此如果您只搜索该数据集一次，您已经拥有了最有效的方法。 p>

---

编辑:在评论中，OP 描述了有时需要向 vector 添加新数据。这是一个相当容易解决的问题:只需使用二进制搜索来查找新值在已排序 vector 中的位置，并将其插入那里。