#!/usr/bin/perl -w
use strict;
my @alphas = qw/ 9 4 3 2 22 13 7 140 95 278/;
my @betas = qw/ 8 3 4 1 278 94 15 7 19 200/;
my @results;
foreach my $alpha ( @alphas ) {
foreach my $beta ( @betas ) {
if ( $alpha == $beta ) {
push @results, $beta;
}
}
}
@results = sort { $a <=> $b } @results;
print "Linear search: @results\n";
####
my @alphas = qw/ 9 4 3 2 22 13 7 140 95 278/;
my @betas = qw/ 8 3 4 1 278 94 15 7 19 200/;
my @results;
my %alpha;
@alpha{ @alphas } = undef;
foreach my $beta ( @betas ) {
if ( exists $alpha{ $beta } ) {
push @results, $beta;
}
}
@results = sort { $a <=> $b } @results;
print "Hash lookup: @results\n";
##
##
my @alphas = qw/ 9 4 3 2 22 13 7 140 95 278/;
my @betas = qw/ 8 3 4 1 278 94 15 7 19 200/;
my @results;
my @sorted = sort { $a <=> $b } @alphas;
foreach my $beta ( @betas ) {
my $index = binary_search( \@sorted, $beta );
if ( defined $index ) {
push @results, $beta;
}
}
@results = sort { $a <=> $b } @results;
print "Binary search: @results\n";
sub binary_search {
my ( $array, $target ) = @_;
my ( $low, $high ) = ( 0, scalar @$array );
while ( $low < $high ) {
use integer;
my $current = ( $low + $high ) / 2;
if ( $array->[$current] < $target ) {
$low = $current + 1;
} else {
$high = $current;
}
}
if ( $low < @$array and $array->[$low] == $target ) {
return $low;
} else {
return undef;
}
}