[prev in list] [next in list] [prev in thread] [next in thread] 

List:       perl-beginners
Subject:    Re: help on example from "mastering algorithm with perl" on binarysearch
From:       rich.japh () gmail ! com
Date:       2009-06-27 21:39:19
Message-ID: 193785805-1246138583-cardhu_decombobulator_blackberry.rim.net-1388725071- () bxe1213 ! bisx ! prod ! on ! blackberry
[Download RAW message or body]

Thank you.

Its very clear now.
-----Original Message-----
From: "John W. Krahn" <jwkrahn@shaw.ca>

Date: Sat, 27 Jun 2009 10:46:28 
To: Perl Beginners<beginners@perl.org>
Subject: Re: help on example from "mastering algorithm with perl" on binary
 search


rich lee wrote:
> Hello everyone,

Hello,

> I am trying to read "mastering algorithm with perl" and below example has me
> bit stuck.
> I understand everything except these 2 lines
> 
> 
>             $low = $try + 1, next if $array->[$try] lt $word;
>             $high = $try -1, next if $array->[$try] gt $word;

Those two lines are short for:

if ( $array->[ $try ] lt $word ) {
     $low = $try + 1;
     next;
     }
if ( $array->[ $try ] gt $word ) {
     $high = $try - 1;
     next;
     }


> I understand what it's doing but I am not sure how they are being ran.
> For example,  Let's say in one particular turn, $array->[$try] is greater
> than $word...
> I am trying to understand how it skips this line ---> $low = $try + 1, next
> if $array->[$try] lt $word;

If $array->[$try] is greater than $word then it cannot be less than 
$word, or equal to $word at the same time.


> when I look at above 2 lines, it looks like they should be processed
> sequentially.  Meaning $low = $try + 1 should be processed everytime...and
> $high=$try-1 should be
> processed everytime....

No, only "if $array->[$try] lt $word" is processed every time.


> In reality(after looking at the explanation), it should only lower or raise
> when $array->[$try] is either less than(then it should raise the bottom) and
> greater( should lower the top)
> I think I am just not understanding the syntax on above 2 lines.. can
> someone please describe it for me(or am i missing the precedence of the
> relationship of the line??
> 
> 
> $index = binary_search( \@array, $word )
> 
> sub binary_search {
>     my ($array, $word) = @_;
>     my ($low, $high)    = ( 0, @$array - 1 );
> 
>     while ( $low <= $high ) {
>             my $try = int( ($low+$high)/2 );
>             $low = $try + 1, next if $array->[$try] lt $word;
>             $high = $try -1, next if $array->[$try] gt $word;
> 
>             return $try; #we've found the word!
>      }
>      return;             #the word isn't there
> }


John
-- 
Those people who think they know everything are a great
annoyance to those of us who do.        -- Isaac Asimov

-- 
To unsubscribe, e-mail: beginners-unsubscribe@perl.org
For additional commands, e-mail: beginners-help@perl.org
http://learn.perl.org/




[prev in list] [next in list] [prev in thread] [next in thread]