Re:Nearly All Binary Searches and Mergesorts are Broken (2006)
by PhantomGremlin on Thursday July 09, 2015 @04:59PM
(#9860641)
it's not really buying you much
I strongly agree. There's a certain elegance in fixing the bug, but it has little practical significance. If you're processing arrays with a billion or more elements, you need to be doing that in a 64-bit environment. In fact you are in a 64 bit environment, because your data won't even fit into a 32 bit address space.
End of story.
Edit: just to be pedantic, and to forestall arguments, when I say "64-bit environment", that means pointers, array indexes, etc are all 64 bits. Using 32 bit ints just doesn't work.
Of course if you have ~2^31 elements it's going to fail anyway so it's not really buying you much. Instead your much better off using Longint or at least unsigned int for large arrays.
PS: int mid = (low + high) >>> 1; might work assuming overflow's are ignored, but you might endup with the same bug.