3 ms·
Is it worth to make the algorithm faster at the cost of throwing surprise OutOfBounds exceptions in some extreme edge cases? Maybe, but only if you - and only
by javcasas 2y ago
Is it worth to make the algorithm faster at the cost of throwing surprise OutOfBounds exceptions in some extreme edge cases?
Maybe, but only if you - and only you,and not an attacker can control the case you are in.
- xigoi 2y agoIf an attacker can somehow make sure that there is an array with 2³⁰ elements, you have worse problems than a binary search crashing.
- javcasas 2y agoWhy do you think this algorithm only applies to arrays? Why do you think this algorithm doesn't apply to this sine lookup table that the compiler placed at the end of the memory in the microcontroller?
- deleted 2y ago[deleted]
- xigoi 2y agoBecause the article is about binary searching an array. Obviously algorithms must be adapted to what they are used for.
- javcasas 2y agoSure, because my pre-computed table isn't an array. It's just a bunch of numbers in consecutive positions in memory. That has never been an array. Also, what makes you think I'm not adapting the algorithm? I mean, I set the search indexes at the address of the beginning and end of the totally-not-an-array array so as to not have to do a relative memory read, because those are not supported in my microcontroller, or if they are supported, it's an extra cycle, and my timing budget is quite tight. Also, I don't do a div by 2, but a shift right by 1, same reason.
- ajuc 2y agoIt's as simple as replacing one NULL character with something else. Or 1 length field.