3 ms·
Even with unsigned int (or even size_t), the C/C++ code still doesn't sit well with me. The addition can still overflow, and while unsigned overflow is well-def
by deathanatos 9y ago
Even with unsigned int (or even size_t), the C/C++ code still doesn't sit well with me. The addition can still overflow, and while unsigned overflow is well-defined, the result here is still nonsense. (i.e., while the result of (low + high) >> 1 during overflow will be well defined, it won't be the midpoint…)
You might argue that you're never going to overflow a size_t on a 64-bit, maybe, but given that the correct code is right there above in the article, it seems easy enough to just do the right thing (add half the delta to the lower bound, which avoids overflow all together for unsigned integer inputs).
- GuB-42 9y agoWith size_t, it would never overflow, even on 32 bits. The input is an array of int, ints are 4 bytes, 32 bit systems can only address 2^32 bytes, so the array is no more than 2^30 elements long, so in the worst case, low+high equals 2^31-3, less than even a signed it. It could overflow if we pass it a char* instead but if you have a >2GB array of sorted single bytes, you probably have a problem somewhere else...