Although binary search is straightforward, the details can be tricky

Today I found myself (once more) commenting to someone how tricky implementing something as basic as binary search can be. Not the first time, either, that I receive an incredulous "you think so?" from my interlocutor. So I began to think why was it that I thought this. I found the answer in this article, with a quote from the very Knuth himself.

I'm pretty sure I read both the Knuth, Bentley and Bloch notes about this at some point, and basically made the quote part of my beliefs system :-).

The article from J. Bloch also makes for an interesting, short read [1]. In a nutshell the piece of the algorithm that implements the pivot index is often implemented like this:

int mid = (low + high) / 2;

... which is incorrect because (low + high) introduce the risk of overflow for big enough indexes overflowing the int capacity. Possible solution:

int mid = low + ((high - low) / 2);

1: http://googleresearch.blogspot.com/2006/06/extra-extra-read-...