Indeed, Java's binary search had this bug for a while! It was found through automatic verification, by the way.

https://ai.googleblog.com/2006/06/extra-extra-read-all-about...

also some CS books

Incidentally, as outlined in this Julia FAQ, native machine arithmetic with overflow will deal with this correctly.

    mid = (lo + hi) >>> 1

https://docs.julialang.org/en/v1/manual/faq/index.html#Why-d...

EDIT: legibility

Thank you, fixed it!

const mid = Math.floor(left + (right - left) / 2);

https://stackoverflow.com/q/27167943

Not in Javascript, where everything is a double precision float. You would lose precision at about 2^51, but that’s not a limit that will meaningfully affect us for good while.

Oh really? And what if you aren't storing the data? You just want to find such n, that f(n) >= m and f(n+1) < m. Now perhaps it might become an issue.