有效地在浮点数数组中找到最接近的值

Question

给定一个(排序)数组a和参考值b我想找到值x∈A与b的绝对差最小高效。

是相当大的(最小数量级是10 26个元素)。

我的第一个天真的方法是计算如下(用Julia写的):

function find_closest(array, element)
argmin(abs.(array .- element))
end

我想知道你能做得更好。不幸的是，大多数相关问题都是处理整数的。

Answer 1

SinceA已经排序，使用

应该会更快

function find_closest(A::AbstractArray{T}, b::T) where {T<:Real}
if length(A) <= 1
return firstindex(A)
end
i = searchsortedfirst(A, b)
if i == firstindex(A)
return i
elseif i > lastindex(A)
return lastindex(A)
else
prev_dist = b - A[i-1]
next_dist = A[i] - b
if prev_dist < next_dist
return i - 1
else
return i
end
end
end

由于searchsorted类函数在O(log n)中执行。