Beefy Boxes and Bandwidth Generously Provided by pair Networks
Clear questions and runnable code
get the best and fastest answer
 
PerlMonks  

Binary vs. linear search

by reisinge (Hermit)
on Nov 12, 2018 at 12:46 UTC ( [id://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 (Monsignor) 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 (Parson) on Nov 13, 2018 at 05:51 UTC

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
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?Last hourOther CB clients
Other Users?
Others making s'mores by the fire in the courtyard of the Monastery: (6)
As of 2024-03-28 08:37 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found