Java 中二分查找取中间值的这个公式 int mid = low + (high - low)/2;，是数学中的什么公式啊？这个是什么原理啊？

[burnbrid]

java 中二分查找取中间值的这个公式，是数学中的什么公式啊？我知道这样写是为了防止数值溢出，int mid = low + (high - low)/2; 但是我想知道这个是数学里面的什么公式？ 正常来说求中间值不就是最大数 + 最小数 再除以 2 = 中间数。比如 1 和 9 。1 + 9 = 10 10 /2=5，5 刚好就是中间数,但是这个公式我搞不懂 int mid = low + (high - low)/2;

[linauror]

防止溢出的求中间值写法

[linauror]

比如：int max = INT_MAX
int low = max - 2
int high = max - 1
如果直接求 mid，high+low 就溢出了

[zxCoder]

画个图看看，一个短线和一个长线的平均数，不就是等于短线加上他俩中间相差部分的一半？

[morrieati]

一样的，low + (high - low) / 2 == low + high / 2 - low / 2 == high / 2 + low / 2 == (high + low) / 2

[abelmakihara]

你都知道是为了防止数值溢出的了
不考虑这个 low + (high - low)/2 不就等价于(high+low)/2 吗

[hello2060]

同学 (a + b) /2 不就是 a + (b - a) /2 吗 ？

(b - a) /2 就是 ab 间距离的一半，从 a 开始走这一半，不就到 ab 中间点了吗？

[imn1]

数学理论是一样的
计算机这样写，是因为 h 和 l 都没有溢出，但 h+l 有可能溢出了，l+(h-l)/2 能确保不会溢出

[jdhao]

这都水一贴。。

[zcqshine]

@linauror 终于明白为毛不直接(high+low)/2 了

[Kasumi20]

上 BigInteger 就可以

[jdhao]

@jdhao java 官方的二分搜索之前也有这个 bug，没考虑溢出，后面被修复了。之前做 leetcode 也遇到过这个问题 https://jdhao.github.io/2017/08/27/binary-search-overflow-issue/

[dswyzx]

除法展开.是义务教育的范畴吧

[PopRain]

小学生都会的推导过程。。。。。

[BBCCBB]

....楼主你...

[violence123456]

你这数学功底太感人了吧，low+（ high-low ）/2 不就等于（ low+high ）/2 ？😂

[wshwwl]

这样的也能编程，我对自己的肯定又多了一分，挺住

[Cielsky]

一条线段的起点地址加上线段长度的一半不就是中间位置的地址吗😂

[redtea]

int mid = (low + high) >>> 1;

[yy77]

即使 high low 都在数据类型的范围内，但是 low + high 就可能溢出。用 int mid = low + (high - low)/2 就能避免溢出。

[Mutoo]

证：
(low + high) / 2 =
low / 2 + high / 2 =
(low - low / 2) + high / 2 =
low + (high - low) / 2

证毕