使用二分搜索在向量中查找最接近的值

Question

假设是一个愚蠢的玩具例子

x=4.5
w=c(1,2,4,6,7)

我想知道是否有一个简单的R函数找到与xin 最接近的匹配的索引w.所以,如果foo是那个功能,foo(w,x)将返回3.该功能match是正确的想法,但似乎只适用于完全匹配.

这里的解决方案(例如which.min(abs(w - x)),which(abs(w-x)==min(abs(w-x)))等等)都是O(n)代替log(n)(我假设w已经排序).

Answer 1

您可以使用data.table二进制搜索:

dt = data.table(w, val = w) # you'll see why val is needed in a sec
setattr(dt, "sorted", "w")  # let data.table know that w is sorted

请注意,如果列w尚未排序,则必须使用setkey(dt, w)而不是setattr(.).

# binary search and "roll" to the nearest neighbour
dt[J(x), roll = "nearest"]
#     w val
#1: 4.5   4

在最后一个表达式中,该val列将具有您正在寻找的内容.

# or to get the index as Josh points out
# (and then you don't need the val column):
dt[J(x), .I, roll = "nearest", by = .EACHI]
#     w .I
#1: 4.5  3

# or to get the index alone
dt[J(x), roll = "nearest", which = TRUE]
#[1] 3

Answer 2

R>findInterval(4.5, c(1,2,4,5,6))
[1] 3

将通过价格合适的匹配来做到这一点(最接近而不会过去).

Answer 3

match.closest()从MALDIquant包中看到：

> library(MALDIquant)
> match.closest(x, w)
[1] 3