アルゴリズムバイナリサーチリターン範囲のPerl

Question

私はフローティングのmilionsとつのアレイを持っている番号（順序付け）し、別の小さい方を指し、iは値の間に重なりが大きいに存在しない（一定の許容範囲内の番号と一致する必要があります配列と小さな配列の値）を大きな配列の小さな配列から削除します。大したことではありません。これは許容範囲内で完璧でない一致を返すためのperl関数です。それはforループ内にあります。小さな配列値をループしています。

sub bin_search{ 
my ($arr, $v, $t) = @_; 
my ($min, $max) = (0, @$arr-1); 
while ($min <= $max) { 
    my $w = $v + $t; 
    my $k = $v - $t; 
    my $try = int(($min + $max)/2); 
    $min = $try + 1, next if $arr -> [$try] < $k ; 
    $max = $try - 1, next if $arr -> [$try] > $w ; 
    return $arr -> [$try] ; 
    } 
return 0; 
} 

しかし、私のデータをチェックインした後、ちょうど最初のマッチを返すので、いくつかの値が破棄されているようです。 私はgrepを試みましたが、遅すぎます。私は1試合があり、一度考えたので

my $min = $val - $t; 
my $max = $val + $t; 
my @arr2 = grep { ($_ > $min) && ($_ < $max) }@big_arr1; 

はので、私は、$分$ maxの範囲を返すためのバイナリ検索を少し変更したかったのいずれかである$分または$ maxの時、そう

のようなもの

sub bin_search{ 
my ($arr, $v, $t) = @_; 
my ($min, $max) = (0, @$arr-1); 
my $w = $v + $t; 
my $k = $v - $t; 
while ($min <= $max) { 
    my $try = int(($min + $max)/2); 
    $min = $try + 1, next if $arr -> [$try] < $k ; 
    $max = $try - 1, next if $arr -> [$try] > $w ; 
    last; 
    } 
my @fin; 
if (($arr -> [$try] < $w) && ($arr -> [$try] > $k)) { 
    push @fin, $arr ->[$try]; $try++ } 
return \@fin; 
} 

でも値が不足していますが、私は何か不足していると思います。私たちが下限に達するまで左のようにしてから$ tryに戻り、上限まで同じことをしますか？バイナリ検索を使用して、一致する要素のインデックスを見つけることによって

Answer 1

スタート。

あなたは範囲が始まる場所を見つける必要がある、ということしたら。バイナリ検索も使用できますが、一致する要素の数が通常少ない場合は、線形検索も可能です。

は最後に、あなたは、範囲の終わりを見つける必要があります。範囲の開始点を見つけるために使用したのと同じアプローチを使用できます。

あなたの解決策の問題点は、範囲の開始を見ていないということです。

次は（あなたのような）リニアスキャンアプローチを使用してテストされていない実装であるので、それは非常に少数のマッチング要素があることを前提としています

sub binsearch_numeric_range { 
    my $min = shift; 
    my $max = shift; 
    my $array = shift; 

    return() if !@$array; 

    my $i = 0; 
    my $j = $#$array; 

    my $k; 
    while (1) { 
     $k = int(($i+$j)/2); 

     if ($array->[$k] > $max) { 
     $j = $k-1; 
     return() if $i > $j; 
     } 
     elsif ($array->[$k] < $min) { 
     $i = $k+1; 
     return() if $i > $j; 
     } 
     else { 
     last; 
     } 
    } 

    my $min_k = $k; --$min_k while $min_k > 0  && $array->[$min_k - 1] >= $min; 
    my $max_k = $k; ++$max_k while $max_k < $#$array && $array->[$max_k + 1] <= $max; 

    return @$array[$min_k .. $max_k]; 
} 

my @matches = binsearch_numeric_range($v-$t, $v+$t, $arr); 

---

必要としない実装全く新しいbinsearchを書く：

my $idx = binsearch { abs($a-$b) <= $t ? 0 : $a <=> $b } $v, @$arr; 

my @range; 
if ($idx >= 0) { 
    my $min_idx = $idx; --$min_idx while $min_idx > 0  && $arr->[$min_idx-1] >= ($v-$t); 
    my $max_idx = $idx; ++$max_idx while $max_idx < $#$arr && $arr->[$max_idx+1] <= ($v+$t); 

    @range = @$array[$min_idx .. $max_idx]; 
} 

使用binsearchがhere定義されています。