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

What is the meaning of :w in the code?

:w is vi's save ("write") command. He must have tried to save while in edit mode.

Why are you modifying $try? It always gets assigned from int(($lo + $hi)/2) at the top of the loop.

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

Replies are listed 'Best First'.
Re^3: Binary search algorithm.
by jwkrahn (Abbot) on Aug 13, 2011 at 05:36 UTC
    Yes, but $hi or $lo changes in every loop pass.

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

[reply]
[d/l]
[select]
      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.
[reply]

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

        [download]
[reply]
[d/l]
[select]

In Section Cool Uses for Perl