4 ms·
Perhaps instead of being mean, you could be helpful and post a link to said answer.
by jules 8y ago
Perhaps instead of being mean, you could be helpful and post a link to said answer.
- raymond_goo 8y agoWith 64 bit variables it probably works. But for less here is the correct implementation: https://ai.googleblog.com/2006/06/extra-extra-read-all-about-it-nearly.html https://ai.googleblog.com/2006/06/extra-extra-read-all-about...
- jules 8y agoThis implementation: mid = ((unsigned int)low + (unsigned int)high)) >> 1; essentially extends the bit width from 31 bit to 32 bit by going from signed to unsigned, and is thus correct up to array lengths of order 2^31 rather than 2^30. Using an even larger bit width should classify as at least as correct as this. In summary, (low + high)/2 or (low + high) >> 1 is correct up to 2^30 for 32 bit signed and up to 2^62 for 64 bit signed, up to 2^31 for 32 bit unsigned, and up to 2^63 for 64 bit unsigned.