3 ms·
Although binary search is straightforward, the details can be tricky
- emmanueloga_ 12y agoToday 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-all-about-it-nearly.html http://googleresearch.blogspot.com/2006/06/extra-extra-read-...