darkskyapp/binary-search — pull request #2 by ConradIrwin (2013-08-29 04:23:19+00:00)
Title: Fix code for huge Arrays

Unfortunately the code to implement a bug-free binary search does not
translate directly from Java to javascript because javascript does not
have signed integers, it has only floats.

This has two effects on the code as written for arrays ~2**31 in size:
Firstly the addition succeeds, because a double can hold every int up
to 2**53.
Secondly the >>> operator takes the number modulo 2**32 (I don't know
why it's defined this way, but it is: http://es5.github.io/#x11.7.3)
and then halves the remainder. This means that if (low + high) is
greater than 2**32, then mid will be off by -2**31.

The easiest way to fix this would be to go back to the "broken" code,
because (low + high) / 2 works just fine for floats. However it seems
like a good idea not to encourage people to further copy and paste
that code, so instead I replaced it by the slightly wordier alternative
bug-free implementation from the blog post.

e.g. low = Math.pow(2, 31) + 10; high = Math.pow(2, 31) + 20

(low + high) >>> 1 == 15
(low + high) / 2 == Math.pow(2, 31) + 15
(low + (high - low) / 2) == Math.pow(2, 31) + 15

This has the added bonus that it works for arrays of size up to 2 ** 53,
at which point (assuming you have the necessary zettabytes of ram) you
can't index into them reliably anyway.