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;

[ccvzz]

@Mutoo 然而你的证明是错的。整数除法的话，你第一个等式就不对。let low=1，high=3，(low+high)/2=2，low/2+high/2=0+1=1

[lrlz]

夹逼准则

[LGA1150]

@redtea #18
负数下溢出会出问题
(Integer.MIN_VALUE * 2) >>> 1 会变成 0

[redtea]

@LGA1150 int mid = low + ((high - low)>>1);

[hello2060]

@ccvzz 不只整数乘法，他这浮点数也不对啊。

[Raven316]

小学毕业了吗

[AmosAlbert]

[suikatw]

@linauror 为什么这么写就可以防止溢出呢？ high-low 感觉还是会溢出吧，比如 high = -INT_MAX, low=INT_MAX

[venster]

@imn1 看了这么多就没几个靠谱的，就你解释的最简洁明了了。

[hello2060]

@suikatw 同学，这是在说 2 分法写程序哇，left > right 的情况早就函数退出了啊

[Ehend]

。。。low+(high-low)/2，第一个 low 你理解为起点的偏移量就行，后面的部分就是取 1/2

[suikatw]

@hello2060 还是不懂，那改一下，high=INT_MAX, low=-INT_MAX 。int mid = low + (high - low)/2; 计算这条语句的时候算到括号里 high-low 不就溢出了么？

[suikatw]

@imn1 为什么会考虑 h+l 溢出但是不考虑 h-l 溢出呢？

[hello2060]

@suikatw 好吧，那就真的溢出了。你是对的。

但是二分法一般用在数组查找啊，left，right 起始值一般是 0 和 array.length - 1 啦，所以 right - low <= INT_MAX

high=INT_MAX, low=-INT_MAX 那肯定还是溢出了

[Ehend]

@suikatw 额，二分查找工程里用的话，哪有序号是负数的。。。即使从 0 开始计数，INT_MAX-0=INT_MAX，这不是还是没溢出吗。。。

[suikatw]

是我忽略了数组下标取值这个前提场景，确实可以防止溢出

[wzcloud]

数学中的公式。。。
mid=(low+high)/2=(low+high+low-low)/2=(2low+high-low)/2=low+(high-low)/2

[jimmyismagic]

我发现越简单的问题，讨论得越多，越没有价值的会，开得越长

[flippydoo]

义务教育的普及有待提高

[lxilu]

@hello2060 @ccvzz，@Mutoo 明明是数学证明