Hacker News Reader

I knew about the infamous Binary Search bugs in books, and I dared to write the first bug-free implementation in my book, very carefully. Still, it ended up having bugs. :) Luckily, Manning's early access program let me fix them before printing.

View on HN

Oh interesting, where can we read about the bug that was there?

It was quite silly. The most common bug with binary search is calculating the middle point: `(start + end) / 2`. It looks straightforward, but "start + end" could cause an integer overflow for large data structures, and that would break the function. IIRC, my handling for that case also turned out to be incorrect, and one of the readers caught it. I don't remember if there were other bugs, there could be, but that one hurt the most :)

Ah yes this is the "classic" bug that was in the Java standard library undiscovered for twenty years, iirc.

I find this topic really interesting, thanks for sharing. I doubt I could code a binary search without any bugs from scratch :)

Reply on news.ycombinator.com