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

[Henrik Bengtsson]

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
_._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._