二進制搜索像概念在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