Beefy Boxes and Bandwidth Generously Provided by pair Networks
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 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

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

Log In?
Username:
Password:

What's my password?
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?
    Notices?