Nearly All Binary Searches and Mergesorts are Broken

The naive implementation of a binary search in a language with machine arithmetic (C, Java, ...) is prone to an overflow error. You can read about it at Joshua Bloch's weblog. Bloch writes:

"The binary-search bug applies equally to mergesort, and to other divide-and-conquer algorithms. If you have any code that implements one of these algorithms, fix it now before it blows up. The general lesson that I take away from this bug is humility: It is hard to write even the smallest piece of code correctly, and our whole world runs on big, complex pieces of code."

It is even harder to write correct code if your language is broken. It is sad that three decades(?) after the "number tower" became a common fixture of Lisp systems, we still have programmers struggling with integer overflow issues.