在整数数组中查找最接近的数字

Question

给定一个排序整数数组，我想找到最接近给定数字的值。数组可能包含重复值和负数。一个例子：输入 :arr[] = {-5, 2, 5, 6, 7, 8, 8, 9}; 目标数 = 4 输出：5

哪种算法最快？二分查找？ STL 查找算法？

感谢您的帮助。

Answer 1

std 库中有一个算法几乎完全符合您的要求：std::lower_bound

Returns an iterator pointing to the first element in the range [first, last) that is not less than (i.e. greater or equal to) value, or last if no such element is found.

您可以使用它来查找等于或高于目标的第一个元素。答案是它前面的那个数字。

检查以下示例：

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 执行二进制搜索。这比一个简单的解决方案要快得多，在这个解决方案中，您将遍历整个集合并逐一检查每个元素。

在整数数组中查找最接近的数字

Find closest number in integer array

c++

arrays

closest