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 :)
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 :)