Nearly all binary searches and mergesorts are broken (2006)

> (2006)

In the very least,this should feature in the title. In fact, previous submissions from over a decade ago also feature year in the title.

Otherwise it conveys the idea that this is some major epiphany.

Thanks!

It was certainly possible to run the algorithm on 16GB of array before the moment when it happened but did the original developer have that sort of space on their desktop at the time? Possibly not.

If a unit test only runs on a server and not on the laptops of the developers then its not going to be written, whereas ideally someone should write a test that is tagged to only run on the server but that is a lot of extra work if that isn't a common thing on a project. Even now I would be quite wary of producing a max size input test for an array of ints and especially objects, that is going to raise some questions due to being a slow test and a highly resource consuming one.

If I was worrying about the same in aerospace programming however then no question that test would get written and we would ensure it got run on the hardware that it was designed to run on. In typical business software its less common to run potentially very long running tests and simulations of the machines states everyone wants to go faster than that especially for the sake of a max input test.

> In a binary search, each variable can be zero, one, some(*), max, overflowed. The combination of these is not infinite as the values of some that cause different behavior is much more reasonable when grouped into chunks of the same behavior.

You are presuming that the algorithm is correct in the first place. Contrived example.

   binary_search(array, key) {
     if (key == 453) explode_world()
     //Do correct binary search.
   }

  > each variable can be zero, one, some(*), max, overflowed

Are you quantizing information?

You mean property testing ? QuickCheck would be the go to library ( the original is in Haskell, however most languages have one ).

can also be spotted with experience.

these kinds of problems are present in very many standard treatments of algorithms and don't survive their first contact with real world use in some cases.

"needs a carry bit or a wider type" is common for arithmetic operations that actually use the range.

C++ added std::midpoint() to the standard library: https://en.cppreference.com/w/cpp/numeric/midpoint

Another fun case, besides integer overflow, is negative values: in Java and C/C++ (i + j)/2 will round towards j, but i + (j - i)/2 will round towards i instead. Sometimes the difference matters.

I was thinking the same. And the code would be clearer too.

Sometimes they’re engineered and tested for a certain scale.

More often they’re engineered and tested for an arbitrary scale. The limits aren’t considered, behavior at the edges isn’t accounted for, and it’s assumed it will be good enough for real world inputs.

The use of `int` tends to be a dead giveaway. There are some cases where it’s clearly correct: where the spec says so (like argv), where you’re starting from a smaller type and it’s impossible for the calculations to overflow in an int (like adding two uint8), that sort of thing. And there are cases where it’s subtly correct, because you know the range of the value is sufficiently limited, either by mechanics or by spec.

But most of the time, int gets chosen because it’s the apparent default and it’s easy to type. No analysis has been done to see if it’s correct or if you want to declare your code to only support inputs in a certain range.

It’s really clear if you’ve written a binary search (or anything else that works on general arrays) in C and you use int as the index type. There’s pretty much no scenario where that makes sense. In theory you could analyze the entire program and prove that over-large arrays are never passed in, and keep doing it to make sure it stays that way, but that’s not realistic. If the programmer actually took one second to think about the appropriate data types, they’d use size_t rather than int.

You can still have this bug with size_t, of course. But it won’t be “this falls apart with arrays over 1G elements on 64-bit systems that can easily handle them.” If you declare that you wrote the obvious midpoint calculation with size_t because you didn’t intend to support byte arrays larger than half the address space, it’s at least plausible.

> certain scale

Make it explicit. If the array is too large, throw an IllegalArgumentException. Document the limit. Then I agree with you.

Otherwise, if an allowed input crashes the program at runtime with a random exception, I respectfully disagree.

The problem is that it's not that much harder to make it work for all the valid inputs.

Not doing that is not good enough.

Another example is summing lots of floats naively instead of using Kahan's algorithm.

It's like we had a theory of gravity that doesn't work on Mars because we have unnecessary division by (m-Mars' mass) in our laws :) It wouldn't be good physics.

> Certain scale

Or just put the algorithm in a 16-bit microcontroller, put some table that needs to be looked up (think precomputed sine table), put that table near the end of the memory range, and just make the mistake to call binary search specifying the start and end memory positions of the table.

These implementations are definitely broken when the specification goes like "you just pass in your array here and it will perform binary search on it for your value." Yes, you could constrain this spec, but come on...

It's such a blatant example for a bug, that I struggle to believe how can anyone even remotely conceive and pivot to the idea that "nuh-uh, this is a bad spec not a bad implementation!".

I would disagree. The inputs to these functions are user controlled and so can be forced to break, whereas humans cannot change how gravity works.

Why do we need to draw that line somewhere? Fixed solution works for a full range of Java int.

Doing any math with bounded integers considered harmful.

At some point during my undergrad I realized this and tried to be really careful when implementing algorithms, but it's stupidly hard to do in a tidy way, at least in old C. It's not practical and people just rather close their eyes and live in blissful avoidance.

And on machines with finite memory, right? Which would be every actual computer ever built?

The difference is that we know for a fact that the proper implementation works for integers up to 2^31, whereas the improper implementation deceived us into thinking that the code would work in situations where the code actually doesn't work.

I find it valuable to understand when my code will crash.

Article was written in 2006 when 32-bit architectures were dominant.

I suppose the issue is moot now on 64-bit architectures, as the difference between 2^62 and 2^63 isn't relevant. (2^62 bytes is 4611686 terrabytes.)

The use of:

   int high = a.length - 1;

Not really. Arrays are limited to an int in size. You would be using more memory for the calculation and have to cast the value down to a 32 bit value to use as an array index.

Or you could just write the code so it isn't vulnerable to integer overflow.

Because it's sort of like premature optimization. If your business case will never be dealing with billion-element arrays, it's a waste of time to make sure your code can handle them.

That's not only wrong in itself, but totally orthogonal.

A binary search implementation should still work, regardless of the array length, or have the limitation documented.

And of course an array "with length over a billion" can be totally valid, depending on the use case, your tradeoffs, available memory, etc. It could even be the optimal data structure for some use cases.

I'm not a Java programmer, but how would you load of a 1GB file into memory? I assume read returns some kind of an array.

Also big arrays being (supposedly) a coffeee smell doesn't mean that code handling them improperly is not buggy.

Relational databases often require searching and sorting gigabytes of data to answer queries (sometimes larger than RAM if e.g. k-way merge sort is used) so it doesn't seem that far-fetched, especially given that there are database systems written in Java.

not doing much scientific programming eh?

I often think AI is mostly crap, wasting a lot of energy for very questionable benefits. But could/should this repetitive task of reminding submitters to follow the submission guidelines and add the year to submissions of old articles be automated?