in reply to Re^2: Binary search algorithm.
in thread Binary search algorithm.

Yes, but $hi or $lo changes in every loop pass.

Yes but that doesn't mean you have to modify $try.

Replies are listed 'Best First'.
Re^4: Binary search algorithm.
by ikegami (Patriarch) on Aug 13, 2011 at 05:54 UTC
    Yes, it does. The algorithm is: Find the halfway point ($try) of the area to search ($lo..$hi). Find in which half the result lies. Repeat.

      After $try is modified, the next instruction is next which goes to the top of the while loop where $try is assigned a new value.    At no point is the value modified by ++$try or --$try used anywhere so you could just do:

      while ( $lo <= $hi ) { my $try = int( ( $lo + $hi ) / 2 ); if ( $array[ $try ] lt $word ) { $lo = $try + 1; # without increment there will be # a dead loop in the 4th case, # see the note at the bottem } elsif ( $array[ $try ] gt $word ) { $hi = $try - 1; } else { return $try } }

        I misunderstood what you mean earlier. I hadn't noticed that $try was being modified in three places (rather than just at the top).

        At no point is the value modified by ++$try or --$try used anywhere so you could just do:

        That's not true. They're assigned to $lo and $hi respectively.

        You probably meant to say that modifying $try here is superfluous. True, but irrelevant. Like you said, $try will get overwritten, so it doesn't matter if gets changed.

        I would actually use +1 and -1, but keep in mind it's actually a teenie weenie bit faster to use pre-increment and pre-decrement.