More 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 += le

More 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.