给定一个有序整数数组，我想找到最接近给定数字的值。数组可能包含重复值和负数。示例：输入：arr [] = {-5、2、5、6、7、8、8、9}；目标数量= 4输出：5
哪个是最快的算法？二进制搜索？STL找到算法了吗？
谢谢你的帮助。
std库中有一种算法几乎可以完全满足您的要求：std::lower_bound
返回一个迭代器，该迭代器指向不小于（即大于或等于）值的[first，last）范围内的第一个元素；如果找不到此类元素，则返回last。
您可以使用它来查找等于或高于目标的第一个元素。答案是前面的那个数字。
检查以下示例：
int find_closest(const vector<int>& A, const int a)
{
if(A.size() <=0)
throw std::invalid_argument("empty array");
const auto lb = std::lower_bound(A.begin(), A.end(), a);
int ans = lb!= A.end() ? *lb : A.back();
if (lb != A.begin()) {
auto prec = lb - 1;
if (abs(ans - a) > abs(*prec - a))
ans = *prec;
}
return ans;
}
在lower_bound执行二进制搜索时，此方法的复杂性在输入集合的大小上是对数的。这比幼稚的解决方案要快得多，在幼稚的解决方案中，您将遍历整个集合并逐个检查每个元素。
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句