4 ms·
Isn't this bit: const mid = Math.floor((right + left) / 2); susceptible to overflow? EDIT: Hm, perhaps not (in JS). Number.MAX_SAFE_INTEGER is much greater t
by JonathanMerklin 8y ago
Isn't this bit:
const mid = Math.floor((right + left) / 2);
susceptible to overflow?
EDIT: Hm, perhaps not (in JS). Number.MAX_SAFE_INTEGER is much greater than I expected.
- josephg 8y agoNot 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.
- enedil 8y agoOh 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.
- netgusto 8y agoThank you, fixed it! const mid = Math.floor(left + (right - left) / 2); https://stackoverflow.com/q/27167943 https://stackoverflow.com/q/27167943
- deleted 8y ago[deleted]
- lou1306 8y agoIndeed, 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-it-nearly.html https://ai.googleblog.com/2006/06/extra-extra-read-all-about...
- agumonkey 8y agoalso some CS books
- FabHK 8y agoIncidentally, 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-does-Julia-use-native-machine-integer-arithmetic?-1 https://docs.julialang.org/en/v1/manual/faq/index.html#Why-d... EDIT: legibility