diff options
| author | drbaggy <js5@sanger.ac.uk> | 2021-05-10 00:24:54 +0100 |
|---|---|---|
| committer | drbaggy <js5@sanger.ac.uk> | 2021-05-10 00:24:54 +0100 |
| commit | d23d45a69aae89960726449e002f64e98a3fd6c4 (patch) | |
| tree | 43d3b7af43c6ea6bad287bdf57e28fff58bb1c2a | |
| parent | 65c8b8f80ba9f702dd1e25c4b4409632dccf954e (diff) | |
| download | perlweeklychallenge-club-d23d45a69aae89960726449e002f64e98a3fd6c4.tar.gz perlweeklychallenge-club-d23d45a69aae89960726449e002f64e98a3fd6c4.tar.bz2 perlweeklychallenge-club-d23d45a69aae89960726449e002f64e98a3fd6c4.zip | |
added diff binary search
| -rw-r--r-- | challenge-111/james-smith/perl/ch-1.pl | 17 |
1 files changed, 17 insertions, 0 deletions
diff --git a/challenge-111/james-smith/perl/ch-1.pl b/challenge-111/james-smith/perl/ch-1.pl index ae3f2e55f5..927633a2c0 100644 --- a/challenge-111/james-smith/perl/ch-1.pl +++ b/challenge-111/james-smith/perl/ch-1.pl @@ -97,6 +97,7 @@ my $tests = { 'DNF' => sub { find_val_dnf( $_, $matrix ) foreach @KEYS; }, 'DNFOpt' => sub { find_val_dnf_optimal( $_, $matrix ) foreach @KEYS; }, 'DNFGen' => sub { find_val_general_dnf( $_, $matrix ) foreach @KEYS; }, + 'Binary' => sub { find_val_binary( $_, $matrix ) foreach @KEYS; }, 'Hash' => sub { find_val_hash( $_, $matrix ) foreach @KEYS; }, 'Flatten@' => sub { flatten_array( $_, @M ) foreach @KEYS; }, @@ -109,6 +110,9 @@ my $tests = { 'preGrep' => sub { find_val_grep_pre( $_, $A ) foreach @KEYS; }, }; +is( find_val_binary( 35, $matrix ), 0 ); +is( find_val_binary( 39, $matrix ), 1 ); +is( find_val_binary( $_, $matrix ), $TEST_SET{$_} ) foreach @KEYS; is( find_val_any_any_naive( 35, $matrix ), 0 ); is( find_val_any_any_naive( 39, $matrix ), 1 ); is( find_val_any_any_naive( $_, $matrix ), $TEST_SET{$_} ) foreach @KEYS; @@ -183,6 +187,19 @@ sub find_val_general_dnf { return 0; } +sub find_val_binary { + my($v,$m)=@_; + return 0 if$v<$m->[0][0]||$v>$m->[-1][-1]; + my $size = @{$m}; + my($v2,$n,$l,$r)=(0,0,0,$size*$size-1); + while($l<=$r) { + $n=($l+$r)>>1; + return 1 if $v == ($v2 = $m->[$n/$size][$n%$size]); + $v>$v2?($l=$n+1):($r=$n-1); + } + return 0; +} + sub find_val_dnf { my($v,$m) = @_; return $v < $m->[0][0] || $v > $m->[4][4] |