Nearly All Binary Searches and Mergesorts Are Broken (2006)

Re:Nearly All Binary Searches and Mergesorts Are Broken (2006) by legulere on Saturday July 23, 2016 @04:11AM (#12148788)

    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);

[ Parent | on HN ]

Re:Nearly All Binary Searches and Mergesorts Are Broken (2006) by abecedarius on Saturday July 23, 2016 @04:45AM (#12148849)

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.

[ Parent | on HN ]