Find closest value in a vector with binary search

Question

As a silly toy example, suppose

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

I wonder if there is a simple R function that finds the index of the closest match to x in w. So if foo is that function, foo(w,x) would return 3. The function match is the right idea, but seems to apply only for exact matches.

Solutions here (e.g. which.min(abs(w - x)), which(abs(w-x)==min(abs(w-x))), etc.) are all O(n) instead of log(n) (I'm assuming that w is already sorted).

Answer 1

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

will do that with price-is-right matching (closest without going over).

Answer 2

You can use data.table to do a binary search:

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 

Note that if the column w isn't already sorted, then you'll have to use setkey(dt, w) instead of setattr(.).

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

In the final expression the val column will have the you're looking for.

# 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