# [R] Fastest way to find the last index k such that x[k] < y in a sorted vector x?

Henrik Bengtsson hb at maths.lth.se
Thu Jun 27 17:12:17 CEST 2002

```Hi, I am trying to find the fastest way to

"find the last index k such that x[k] < y in a *sorted* vector x"

These are my two alternatives:

x <- sort(rnorm(1e4))
y <- 0.2

# Alt 1
k <- max(1, sum(x < y))

# Alt 2 "divide and conquer"
lastIndexLessThan <- function(x, y) {
k0 <- 1; k1 <- length(x)
while ((dk <- (k1 - k0)) > 1) {
k <- k0 + dk %/% 2
if (x[k] < y) k0 <- k else k1 <- k
}
k0
}
k <- lastIndexLessThan(x, y)

Simple benchmarking shows that alternative 1 is faster for short vectors and
alternative 2 is faster for long vectors. I believe this is because alt 1 is
implemented internally. Is there an internal function of alternative 2 that
I don't know about? It would be great because then it would probably be the
fastest one on both short and long vectors.

Best

Henrik Bengtsson

Dept. of Mathematical Statistics @ Centre for Mathematical Sciences
Lund Institute of Technology/Lund University, Sweden (+2h UTC)
Office: P316, +46 46 222 9611 (phone), +46 46 222 4623 (fax)
h b @ m a t h s . l t h . s e, http://www.maths.lth.se/bioinformatics/

-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-
r-help mailing list -- Read http://www.ci.tuwien.ac.at/~hornik/R/R-FAQ.html
Send "info", "help", or "[un]subscribe"
(in the "body", not the subject !)  To: r-help-request at stat.math.ethz.ch
_._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._

```