3 ms·
int mid = (low + high) >>> 1; I don't get how this fixes anything, the overflow still occurs. Why not simply int mid = (low/2) + (high/2) + (low & high &
by legulere 10y ago
int mid = (low + high) >>> 1;
I don't get how this fixes anything, the overflow still occurs.
Why not simply
int mid = (low/2) + (high/2) + (low & high & 1);
- abecedarius 10y agoMore expensive. Here's another approach: represent the range as a (low, length) pair instead of (low, high). The update becomes either length /= 2 or low += length/2, length -= length/2. IIRC this was what I did when I adapted Bentley's code to C 25 years ago, mainly because of overflow. It never occurred to me to check if standard libraries got it wrong.