Nearly All Binary Searches and Mergesorts are Broken (2006)

Re:Nearly All Binary Searches and Mergesorts are Broken (2006) by MaulingMonkey on Tuesday November 26, 2013 @04:12AM (#6800084)

On top of that, this 'fix' from the article, even if it were corrected to use size_t instead of unsigned int...

  In C and C++ (where you don't have the >>> operator), you can do this:
  6:             mid = ((unsigned int)low + (unsigned int)high)) >> 1;

Has the same bug as the original snippet, just in unsigned space. Now, granted, binary searching a >2GB byte array in a 32-bit process is an unlikely use case... but it is technically feasible!

[ Parent | on HN ]

Re:Nearly All Binary Searches and Mergesorts are Broken (2006) by PhantomGremlin on Tuesday November 26, 2013 @05:35AM (#6800330)

Yeah. That "fix" immediately jumped out at me in the sense of WTF??? All he did was double the max size of the array before his code fails again!

That so-called "fixed" code just couldn't do anything useful in a 32-bit address space. A billion 32-bit ints completely fills up the address space by itself. As you note, perhaps it could "technically" be possible to search a billion 8-bit bytes, but that's not what's being passed in to the function.

And if he's running in a 64-bit address space (otherwise how could he pass in an array of a billion ints), then he should be using 64-bit integer arithmetic. (I don't know enough about Java to know how feasible it is to do that).

[ Parent | on HN ]

Re:Nearly All Binary Searches and Mergesorts are Broken (2006) by Jare on Tuesday November 26, 2013 @06:16AM (#6800456)

If you have an array >2GB (I understand this isn't possible in Java), you can't attempt to use ints as indices at all, you need size_t everywhere.

[ Parent | on HN ]