R语言中如何高效查找指定值在有序数组中的插入位置索引

最优实现方案 #

直接使用R基础包自带的findInterval函数即可，该函数专门面向已排序的数值向量设计，内部采用二分查找实现，时间复杂度为O(log n)，相比你当前用which遍历的*O(n)*写法，在数组长度较大时效率提升极为明显。

代码示例 #

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

# 直接调用，返回结果与你现有写法完全一致
findInterval(v, x)
# 输出结果：3

额外说明 #

• 如果你的排序数组是降序排列，只需添加参数decreasing = TRUE即可：findInterval(v, x, decreasing = TRUE)
• 边界场景处理更友好：当目标值小于数组所有元素时返回0，大于所有元素时返回数组长度，不会像max(which(x <= v))那样出现空值警告
• 该函数为R基础包内置的C语言实现，不需要额外安装任何第三方包，性能是所有可选方案里最优的，不需要自己手动实现二分查找逻辑

内容的提问来源于stack exchange，提问作者Patrick