二进制搜索像概念在R中创建子集数据

Question

对于两种情况，我有以下数据集w和关键变量x。

Case 1: 
x = 4 
w = c(1,2,4,4,4,4,6,7,8,9,10,11,12,14,15) 

Case2: 
x = 12 
w = c(1,2,4,4,4,4,6,7,8,9,10,11,12,14,15) 

我想创建这将为x通过搜索数据集w，将在w子集原始数据集大小的数据集下按x的位置的功能。输出将是具有与搜索关键字相同的上限值的较小大小的数据集。下面是我想中的R写入功能：

create_chunk <- function(val, tab, L=1L, H=length(tab)) 
{ 
    if(H >= L) 
    { 
    mid = L + ((H-L)/2) 
    ## If the element is present within middle length 
    if(tab[mid] > val) 
    { 
     ## subset the original data in reduced size and again do mid position value checking 
     ## then subset the data 
    } else 
    { 
     mid = mid + (mid/2) 
     ## Increase the mid position to go for right side checking 
    } 
    } 
} 

在输出我要寻找如下：

Output for Case 1: 
Dataset containing: 1,2,4,4,4,4 

Output for Case 2: 
Dataset containing: 1,2,4,4,4,4,6,7,8,9,10,11,12 


    Please note: 
    1. Dataset may contain duplicate values for search key and 
     all the duplicate values are expected in the output dataset. 
    2. I have huge size datasets (say around 2M rows) from 
     where I am trying to subset smaller dataset as per my requirement of search key. 

新更新：案例3

输入数据：

    date value size  stockName 
1 2016-08-12 12:44:43 10093.40 4 HWA IS Equity 
2 2016-08-12 12:44:38 10093.35 2 HWA IS Equity 
3 2016-08-12 12:44:47 10088.00 2 HWA IS Equity 
4 2016-08-12 12:44:52 10089.95 1 HWA IS Equity 
5 2016-08-12 12:44:53 10089.95 1 HWA IS Equity 
6 2016-08-12 12:44:54 10088.95 1 HWA IS Equity 

搜索关键字是：10089.95 in value colu MN。

预期成果是：

    date value size  stockName 
1 2016-08-12 12:44:47 10088.00 2 HWA IS Equity 
2 2016-08-12 12:44:54 10088.95 1 HWA IS Equity 
3 2016-08-12 12:44:52 10089.95 1 HWA IS Equity 
4 2016-08-12 12:44:53 10089.95 1 HWA IS Equity 

Answer 1

你能做到这一点这需要重复值的照顾。在重复的情况下，其最高位置将被返回。请注意，A应该是非递减顺序。

binSearch <- function(A, value, left=1, right=length(A)){ 
    if (left > right) 
    return(-1) 
    middle <- (left + right) %/% 2 
    if (A[middle] == value){ 
    while (A[middle] == value) 
     middle<-middle+1 
    return(middle-1) 
    } 
    else { 
    if (A[middle] > value) 
     return(binSearch(A, value, left, middle - 1)) 
    else 
     return(binSearch(A, value, middle + 1, right)) 
    } 
} 

w[1:binSearch(w,x1)] 
# [1] 1 2 4 4 4 4 
w[1:binSearch(w,x2)] 
# [1] 1 2 4 4 4 4 6 7 8 9 10 11 12 

然而，正如其在评论中提到的，你可以简单地使用findInterval达到相同的：

w[1:findInterval(x1,w)] 

如你所知，二进制搜索有log(n)顺序，但在?findInterval所述，由于第一个参数的长度为1，所以也受益于log(n)：

函数findInterval查找一个向量x的索引其他vec，后者必须是非递减的。事实上，内部算法使用间隔搜索来确保O（n * log（N））的复杂性，其中，这是微不足道的，等同于应用（外（x，vec，“> =”），sum）长度（x）（和N < - 长度（vec））。对于（几乎）排序的x，它会更快，基本上是O（n）。

编辑

根据您的编辑和新的设置，你可以这样做（假设你的数据在df）：

o <- order(df$value) 
rows <- o[1:findInterval(key, df$value[o])] 
df[rows,] 

或者等价地，利用所提出的binSearch功能：

o <- order(df$value) 
rows <- o[1:binSearch(df$value[o], key)] 
df[rows,] 

数据

x1 <- 4 
x2 <- 12 
w <- c(1,2,4,4,4,4,6,7,8,9,10,11,12,14,15) 
key <- 10089.95 

Answer 2

这里是一个非常简单的解决方案，你可以建立你的函数出这个命令。当然，你必须检查是否x为w，但是这是你的一部分:-)

x <- 12 
w <- c(1,2,4,4,4,4,6,7,8,9,10,11,12,14,15) 

index <- which(x == w) 

w_new <- w[1:index[length(index)]] 
print(w_new) 
#[1] 1 2 4 4 4 4 6 7 8 9 10 11 12