Re^5: Binary search algorithm.

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]

Comment on Re^5: Binary search algorithm. Select or Download Code

Replies are listed 'Best First'.
Re^6: Binary search algorithm. by ikegami (Patriarch) on Aug 13, 2011 at 16:52 UTC
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.	[reply] [d/l] [select]
Re^7: Binary search algorithm. by jwkrahn (Abbot) on Aug 14, 2011 at 18:30 UTC
You probably meant to say that modifying `$try` here is superfluous. No. Because it does the right thing it is not superfluous. it's actually a teenie weenie bit faster to use pre-increment and pre-decrement. So... you are for optimization over clarity? As Donald Knuth has said: We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil	[reply] [d/l]
Re^8: Binary search algorithm. by BrowserUk (Patriarch) on Aug 14, 2011 at 18:44 UTC
So... you are for optimization over clarity? As Donald Knuth has said: Yes. T'is a shame that so few of the many that quote him really understand what they quote. If clarity is your only goal, then why are you using a binary search? A linear search is easier to program correctly and far clearer to read. The very fact that a binary search is being considered means that someone has acknowledged that performance is sometimes important enough, to trade the performance that comes from its complexity, against the simple clarity of grep. And small efficiencies at the core of frequently used, expensive processes -- like searching -- are the exact 3% that should be optimised. If you'd read Knuth rather than just quoting him, you'd know that, Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error. "Science is about questioning the status quo. Questioning authority". In the absence of evidence, opinion is indistinguishable from prejudice.	[reply]
Re^8: Binary search algorithm. by ikegami (Patriarch) on Aug 14, 2011 at 21:06 UTC
So... you are for optimization over clarity? What's unclear?	[reply]