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:
1 comment
[ 3.3 ms ] story [ 11.5 ms ] threadI'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-...