Найти индекс значения в отсортированном векторе в R

Question

У меня есть упорядоченный вектор уникальных целых чисел в R, и я хочу найти индекс ближайшего элемента, но меньшего или равного некоторому значению. Например, для вектора 4 8 15 16 23 42 и значения поиска 17, я хотел бы, чтобы функция возвращала 4, индекс 16. В Python я бы использовал модуль bisect. Есть ли что-то подобное в R?

Answer 1

Вы можете использовать binsearch из gtools пакета, чтобы получить поведение журнала (п) двоичного поиск:

library(gtools) 
x <- c(4, 8, 15, 16, 23, 42) 
binsearch(function(y) x[y]-17, range=c(1, length(x))) 
# $call 
# binsearch(fun = function(y) x[y] - 17, range = c(1, length(x))) 
# 
# $numiter 
# [1] 3 
# 
# $flag 
# [1] "Between Elements" 
# 
# $where 
# [1] 4 5 
# 
# $value 
# [1] -1 6 

Мы можем увидеть масштабирование сублинейного числа итераций с большим примером:

set.seed(144) 
x <- sort(runif(1000000)) 
binsearch(function(y) x[y]-0.5, range=c(1, length(x))) 
# $call 
# binsearch(fun = function(y) x[y] - 0.5, range = c(1, length(x))) 
# 
# $numiter 
# [1] 21 
# 
# $flag 
# [1] "Between Elements" 
# 
# $where 
# [1] 500577 500578 
# 
# $value 
# [1] -1.990702e-07 5.827751e-07