Find closest value in a vector with binary search
r
Solution
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
Problem
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).