4 ms·
int mid = low + ((high - low) / 2); is going to overflow if high and low have different signs. The correct version that works for any high and low is: int m
by mojuba 17y ago
int mid = low + ((high - low) / 2);
is going to overflow if high and low have different signs. The correct version that works for any high and low is:
int mid = sign(high) != sign(low) ?
(high + low) / 2 : low + (high - low) / 2;
- stuff4ben 17y agoTrue, but Java uses signed int's so the former should still work.
- mojuba 17y agoThat's the problem, if one int is negative and the other is positive, (high - low) may overflow.
- amalcon 17y agoIn this particular context, however, that should be just fine: low is clearly initialized to zero, and then only set to the value of this expression +1. As such, barring other bugs, low can never be negative. Your point is valid, though, and worth bearing in mind in other circumstances.