バイナリサーチのような概念でサブセットデータを作成するR

Question

データセットwとキー変数xの2つのケースがあります。

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) 

私は、データセットwを通じてxを検索すると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 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に述べたように

ファンクションfindIntervalは、1つのベクトルxのインデックスを1つの値にしているため、log(n)からも利益を得ます。他のvec、後者は非減少でなければならない。実際には、apply（outer（x、vec、 "> ="）、1、sum）と同等ですが、内部アルゴリズムはO（n * log（N））複雑さを保証する区間検索を使用します。 n < - 長さ（x）（およびN < - 長さ（vec））。 （ほぼ）ソートされたxについては、それはさらに高速になります。基本的にはO（n）です。あなたの編集、新しい設定を1として

EDIT

、あなたは、この（あなたのデータはdfであると仮定）行うことができます：提案binSearch機能を使用して、

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

または同等にします：

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