in reply to Binary Search - revisited

This contains a bug that was mentioned on a Google programmer's blog some time back. You add posmin and posmax together, possibly inducing overflow or promotion to floating point values.

You should of course take the difference of posmin from posmax, divide it by 2, and add the result to posmin.

This came up on perl5-porters mailing list some time ago: the core was also vulnerable to this error. See the summary on use.perl for the background on this issue.

• another intruder with the mooring in the heart of the Perl

Replies are listed 'Best First'.
Re^2: Binary Search - revisited
by educated_foo (Vicar) on Nov 17, 2006 at 04:20 UTC
    If an SV is more than 2 bytes long (which it is), this is not actually a bug. You'll run out of addressable memory before falling off your array. Really, this "every binary search ever has a bug" meme is silly.