R：获取排序向量中元素的索引

I have a sorted vector, let's say

我有一个排序的矢量,比方说

v <- c(1, 1, 2, 3, 5, 8, 13, 21, 34)

Now I want to find the index i of the first element which is bigger than for example a <- 15.

现在我想找到第一个元素的索引i,它大于例如< - 15。

I could do something like i <- which(v > a)[1].

我可以做像我这样的事情 - 哪个(v> a)[1]。

But I want to exploit the fact that v is sorted, which I don't think which cares about.

但我想利用v排序的事实,我认为这并不关心。

I could write it myself and divide the interval recursively in halves and search in those partial intervals...

我可以自己编写它并将这个间隔递归地分成两半并在那些部分间隔中搜索...

Is there any built-in solution? As usual the main issue is speed and my own function would be slower surely.

有没有内置的解决方案?像往常一样,主要问题是速度,我自己的功能肯定会慢一些。

Thank you.

4 个解决方案

#1

For speed-glutton

a <- 10
v <- sort(runif(1e7,0,1000));
Rcpp::cppFunction('int min_index(NumericVector v, double a) {
                  NumericVector::iterator low=std::lower_bound (v.begin(), v.end(), a);
                  return (low - v.begin());
                  }')
microbenchmark::microbenchmark(which(v > a)[1], min_index(v, a), unit="relative")

#Unit: relative
#            expr      min       lq     mean   median      uq      max neval
#which(v > a)[1] 61299.15 67211.58 14346.42 8797.526 8683.39 11163.27   100
#min_index(v, a)     1.00     1.00     1.00    1.000    1.00     1.00   100

#2

There is uniroot. It is using bisection and is faster on much longer vectors.

没有了。它使用二分法,并且在更长的矢量上更快。

v <- c(1,1,2,3,5,8,13,21,34)
a <- 15

root <- uniroot(f = function(x) v[x] - a, interval = c(1, length(v)))
my_index <- floor(root$root)

#3

Just wonder if the following may be useful.

只是想知道以下是否有用。

Filter(function(x) x > 15, v)[1]
#[1] 21
Find(function(x) x > 15, v, right = FALSE, nomatch = NULL)
#[1] 21
Position(function(x) x > 15, v, right = FALSE, nomatch = NA_integer_)
#[1] 8

#4

which isn't exactly slow, so what about min(which()):

这不是很慢,那么min(which()):

v <- c(1,1,2,3,5,8,13,21,34) 
system.time(
  print(min(which(v > 5)))
)
# [1] 6
# user  system elapsed 
  0       0       0

#1