I was trying to get my head around the binary search algorithm. I did it by comparing it to the linear search algorithm
#!/usr/bin/perl
use warnings;
use v5.14;
# Find this word ...
my $find = shift // "";
# ... in this sorted list of words ...
my @words =
qw(alpha bravo charlie delta echo foxtrot golf hotel india juliett k
+ilo lima mike november oscar papa quebec romeo sierra tango uniform v
+ictor whiskey xray yankee zulu);
# ... using two search algorithms
my %search = (
linear => \&linsearch,
binary => \&binsearch,
);
for my $alg ( sort keys %search ) {
say "$alg searching '$find' in [@words] ...";
my $idx = $search{$alg}->( $find, \@words );
say defined $idx ? "found at index $idx" : "not found";
say "";
}
sub binsearch {
my ( $find, $array ) = @_;
my $low = 0;
my $high = @$array - 1;
while ( $low <= $high ) {
my $try = int( ( $low + $high ) / 2 );
say "--> trying at index $try";
$low = $try + 1, next if $array->[$try] lt $find;
$high = $try - 1, next if $array->[$try] gt $find;
return $try;
}
return;
}
sub linsearch {
my ( $find, $array ) = @_;
for ( my $i = 0 ; $i < @$array ; $i++ ) {
my $try = $i;
say "--> trying at index $try";
if ( $array->[$try] eq $find ) {
return $try;
}
}
return;
}
Genius is 1 percent inspiration and 99 percent perspiration. -- Thomas Edison