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?
Asked
Active
Viewed 2,886 times
5
CesiumLifeJacket
- 83
- 1
- 6
-
maybe http://stackoverflow.com/questions/20133344/find-closest-value-in-a-vector-with-binary-search – Rorschach Jul 20 '15 at 21:18
-
1Using rolling joins from data.table package, `data.table(x, key="x")[.(16), roll=-Inf, which=TRUE]` – Arun Jul 20 '15 at 21:35
-
1`findInterval(17, x)` – Khashaa Jul 21 '15 at 02:31
1 Answers
7
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.
jan-glx
- 7,611
- 2
- 43
- 63
-
Unfortunately `findInterval` appears to be 2-3x slower than simply using `which(non_decreasing_haystack == needle)` – zdebruine Jan 19 '22 at 14:30
-
1@zdebruine this probably strongly depends on the size of the `non_decreasing_haystack` and the number of `needle`s. Can you provide an benchmark? – jan-glx Apr 13 '22 at 12:30
-
@zdebruine 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))`. – Ken Williams Mar 15 '23 at 17:57