二分查找mid值计算：两种优化方案的原理及溢出疑问

Great question! Let’s break down both solutions clearly so you understand exactly how they fix the overflow bug and why their logic works.

一、low + (high - low) / 2的设计逻辑 #

首先得搞懂原来的(low + high) / 2为什么会溢出：当low和high都是接近int类型最大值（比如Java里的2^31-1）的数时，它们的和会超过int的存储上限，变成负数（因为有符号整数的最高位是符号位，溢出后符号位会被置1），这时候再除以2得到的结果就完全错误了。

而low + (high - low) / 2本质上是换了一种数学等价的表达方式，从根源上避免了直接相加两个大数：

• 先计算high - low：在二分查找的逻辑里，high始终大于等于low，所以这个差值是一个非负数，而且最大值不会超过int的上限（比如high是2^31-1，low是0，差值还是2^31-1，刚好在int范围内）。
• 把差值除以2：得到的是low到high区间的一半长度。
• 再加上low：相当于从low出发，走区间一半的距离，最终结果和(low + high)/2完全相等，但整个过程没有任何一步会触发整数溢出。

举个简单例子：假设low=1000000000，high=2000000000，直接相加是3000000000，超过了int的最大值2147483647，会溢出变成负数；但用low + (high - low)/2计算的话，high-low=1000000000，除以2是500000000，加上low得到1500000000，完全正确，而且全程没有溢出。

二、为什么(high + low) >>> 1不会溢出？ #

你观察得很仔细——这个写法确实还是计算了high + low，但它利用了无符号右移的特性来“修复”溢出后的结果：

1. 首先，high + low溢出后会变成一个负数（有符号int的特性），但这个负数的二进制表示其实是正确和的二进制被截断后的结果（比如正确和是2^31，二进制是1后面跟31个0，作为有符号int存储时会变成-2147483648）。
2. 无符号右移>>>会把所有位都当成无符号位来处理，也就是说，右移时左边补0，而不是像有符号右移>>那样补符号位。这就相当于把溢出后的负数当成一个无符号的32位整数来处理，此时它的数值其实等于“正确的和”减去2^32（因为int是32位）。
3. 对这个无符号数右移1位，就等效于除以2，最终得到的结果正好等于原本正确的(low + high)/2。

还是拿刚才的例子：low=1000000000，high=2000000000，它们的和是3000000000，二进制是10110011001011001010000000000000，作为有符号int是-1294967296；对这个数做无符号右移1位，得到01011001100101100101000000000000，也就是1500000000，和正确结果完全一致。

简单来说，这个写法允许high + low溢出，但通过无符号右移把溢出后的“错误”数值拉回了正确的轨道。

内容的提问来源于stack exchange，提问作者Soner from The Ottoman Empire