如何有效地在排序数组中查找值的索引？

Question

我有一个排序的值数组和一个值，如下所示：

x <- c(1.0, 3.45, 5.23, 7.3, 12.5, 23.45)
v <- 6.45

我可以找到在保持排序顺序的同时将v插入到x中的值的索引：

max(which(x <= v))
[1] 3

代码很好而且紧凑，但我有一种直觉，在幕后这是非常低效的：因为which（）不知道数组已排序，所以它必须检查所有值。

有没有更好的方法找到这个指数值？

注意：我对实际合并v到x不感兴趣，我只想要索引值。

Answer 1

如果您需要更快的版本，并且不需要检查输入，您可以编写easy cpp函数：

Rcpp::cppFunction(
  "int foo(double x, const Rcpp::NumericVector& v)
  {
    int min = 0;
    int max = v.size();
    while (max - min > 1)
    {
      int idx = (min + max) / 2;
      if (v[idx] > x)
      {
        max = idx; 
      }
      else
      {
        min = idx;
      }
    }
    return min + 1;
  }"
)

如果需要，您可以检查If（x

library(microbenchmark)

n = 1e6
v = sort(rnorm(n, 0, 15))
x = runif(1, -15, 15)
microbenchmark(max(which(v <= x)), sum(v <= x), findInterval(x, v), foo(x, v))

结果：