Is there a bug in your binary search? According to

Joshua Bloch there maybe one lurking just outside of the range of your bounds test. What is even more surprising to Josh is that this bug is contained in a program that had been proven correct in chapter 5 of Programming Pearls. Though the condition is well known, it still remains somewhat obscure.

So what's the bug? Here's a standard binary search, in Java. (It's one that I wrote for the java.util.Arrays):
1: public static int binarySearch(int[] a, int key) {
2: int low = 0;
3: int high = a.length - 1;
4:
5: while (low <= high) {
6: int mid = (low + high) / 2;
7: int midVal = a[mid];
8:
9: if (midVal < key)
10: low = mid + 1;
11: else if (midVal > key)
12: high = mid - 1;
13: else
14: return mid; // key found
15: }
16: return -(low + 1); // key not found.
17: }

The bug, found in line 16, is of course due to arithmetic overflow. If adding low + high > 2^31 â€“ 1 (maximum value of int), then the value will become negative. There is no need to guess at the consequences of using a negative array index.
So how does one fix such a bug? Josh suggests the formulation; low + ((high - low) / 2). This has the effect of avoiding overflow but involves several extra operations. He suggests a faster version; (low + high) >>> 1. This formula assumes that right sifting a register fills the left most bit with a 0. Since this story is based on a bad assumption.... Of course Josh address this point.

And now we know the binary search is bug-free, right? Well, we strongly suspect so, but we don't know. It is not sufficient merely to prove a program correct; you have to test it too.

He does point out that it is often not possible to completely test an application for all ranges of input and that the problem is worse if not impossible, when testing concurrent programs.
Care to share your favorite hideous bug with us?