未分類
2020 年 12 月 9 日

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

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

資深大佬 : burnbrid 1

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

大佬有話說 (41)

  • 資深大佬 : 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

    证毕

  • 資深大佬 : 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

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

  • 資深大佬 : 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 明明是数学证明

  • 資深大佬 : hello2060

    @lxilu 哈哈 我是故意逗他的嘿嘿