Welcome to the Monastery PerlMonks

### Binary vs. linear search

by reisinge (Hermit)
 on Nov 12, 2018 at 12:46 UTC ( #1225630=CUFP: print w/replies, xml ) Need Help??

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 "";
}

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

Replies are listed 'Best First'.
Re: Binary vs. linear search
by Eily (Monsignor) on Nov 12, 2018 at 13:32 UTC

++ for the good work, the code is well written and structured, not much else to add.

FYI though, the last item of @array is at the index \$#array. This means that the two following lines are equivalent

```my \$high = @\$array - 1;
my \$high = \$#\$array;
And the for loop could be rewritten as
```for my \$try ( 0..\$#\$array ) {
say "--> trying at index \$try";
if ( \$array->[\$try] eq \$find ) {
return \$try;
}
}

Re: Binary vs. linear search
by bliako (Vicar) on Nov 12, 2018 at 13:12 UTC

reisinge, great demo!

A sidenote to the uninitiated: binary search requires a sorted array of words. It is not a coincidence that your @words is sorted.

Re: Binary vs. linear search
by swl (Deacon) on Nov 13, 2018 at 05:51 UTC

Create A New User
Node Status?
node history
Node Type: CUFP [id://1225630]
Approved by Corion
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others avoiding work at the Monastery: (8)
As of 2019-10-17 08:53 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
In 2019 the site I miss most is:

Results (42 votes). Check out past polls.

Notices?