Find index of value in a sorted vector in R

Question

I have an ordered vector of unique integers in R and I want to find the index of the element closest to but less than or equal to some value. For example, for the vector 4 8 15 16 23 42 and the search value 17, I would like the function to return 4, the index of 16. In Python, I would use bisect module. Is there anything similar in R?

Erotomania

maybe #20133844 – Ivetteivetts

Using rolling joins from data.table package, data.table(x, key="x")[.(16), roll=-Inf, which=TRUE] – Depone

findInterval(17, x) – Elisabethelisabethville

Answer 1

Base R provides findInterval, which implements a binary search:

findInterval(17, c(4, 8, 15, 16, 23, 42))

---

@Khashaa already mentioned this in a comment.

Katzenjammer

Unfortunately findInterval appears to be 2-3x slower than simply using which(non_decreasing_haystack == needle) – Hallucination

@Hallucination this probably strongly depends on the size of the non_decreasing_haystack and the number of needles. Can you provide an benchmark? – Katzenjammer

@Hallucination well, your which() solution wouldn't work for this, because none of the values are equal to the target. You could do which.min(abs(non_decreasing_haystack - needle)). – Anthropolatry