Nearly all binary searches and mergesorts are broken (2006)
I'd put the blame on languages that don't allow exceptions, and whose return value in case of errors belong to the same domain as the solution.<p>I've coded binary searches and sorts tons of times in C++, and yet none was succeptible to this bug. Why? Because, whenever you're talking indices, you should ALWAYS use unsigned int. Since an array can't have negative indices, if you use unsigned ints the problem is solved by design. And, if the element is not found, you throw an exception.<p>Instead, in C you don't have exceptions, and you have to figure out creative ways for returning errors. errno-like statics work badly with concurrency. And doing something like int search(..., int* err), and setting err inside of your functions, feels cumbersome.<p>So what does everyone do? Return a positive int if the index is found, or -1 otherwise.<p>In other words, we artificially extend the domain of the solution just to include the error. We force into the signed integer domain something that was always supposed to be unsigned.<p>This is the most common cause for most of the integer overflows problems out there.