V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
burnbrid
V2EX  ›  Java

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

  •  
  •   burnbrid · 2020-12-07 10:46:50 +08:00 · 4659 次点击
    这是一个创建于 569 天前的主题,其中的信息可能已经有所发展或是发生改变。

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

    43 条回复    2020-12-19 22:07:41 +08:00
    linauror
        1
    linauror  
       2020-12-07 10:49:13 +08:00   ❤️ 3
    防止溢出的求中间值写法
    linauror
        2
    linauror  
       2020-12-07 10:50:47 +08:00   ❤️ 7
    比如:int max = INT_MAX
    int low = max - 2
    int high = max - 1
    如果直接求 mid,high+low 就溢出了
    zxCoder
        3
    zxCoder  
       2020-12-07 10:51:25 +08:00
    画个图看看,一个短线和一个长线的平均数,不就是等于短线加上他俩中间相差部分的一半?
    morrieati
        4
    morrieati  
       2020-12-07 10:52:16 +08:00
    一样的,low + (high - low) / 2 == low + high / 2 - low / 2 == high / 2 + low / 2 == (high + low) / 2
    abelmakihara
        5
    abelmakihara  
       2020-12-07 10:53:24 +08:00
    你都知道是为了防止数值溢出的了
    不考虑这个 low + (high - low)/2 不就等价于(high+low)/2 吗
    hello2060
        6
    hello2060  
       2020-12-07 10:54:53 +08:00   ❤️ 1
    同学 (a + b) /2 不就是 a + (b - a) /2 吗 ?

    (b - a) /2 就是 ab 间距离的一半,从 a 开始走这一半,不就到 ab 中间点了吗?
    imn1
        7
    imn1  
       2020-12-07 10:57:15 +08:00   ❤️ 1
    数学理论是一样的
    计算机这样写,是因为 h 和 l 都没有溢出,但 h+l 有可能溢出了,l+(h-l)/2 能确保不会溢出
    jdhao
        8
    jdhao  
       2020-12-07 10:57:17 +08:00 via Android
    这都水一贴。。
    zcqshine
        9
    zcqshine  
       2020-12-07 11:08:57 +08:00
    @linauror 终于明白为毛不直接(high+low)/2 了
    Kasumi20
        10
    Kasumi20  
       2020-12-07 11:21:58 +08:00
    上 BigInteger 就可以
    jdhao
        11
    jdhao  
       2020-12-07 11:24:13 +08:00 via Android   ❤️ 1
    @jdhao java 官方的二分搜索之前也有这个 bug,没考虑溢出,后面被修复了。之前做 leetcode 也遇到过这个问题 https://jdhao.github.io/2017/08/27/binary-search-overflow-issue/
    dswyzx
        12
    dswyzx  
       2020-12-07 12:09:33 +08:00
    除法展开.是义务教育的范畴吧
    PopRain
        13
    PopRain  
       2020-12-07 12:33:13 +08:00
    小学生都会的推导过程。。。。。
    BBCCBB
        14
    BBCCBB  
       2020-12-07 12:35:32 +08:00
    ....楼主你...
    violence123456
        15
    violence123456  
       2020-12-07 12:38:10 +08:00 via iPhone
    你这数学功底太感人了吧,low+( high-low )/2 不就等于( low+high )/2 ?😂
    wshwwl
        16
    wshwwl  
       2020-12-07 12:47:52 +08:00 via iPhone   ❤️ 5
    这样的也能编程,我对自己的肯定又多了一分,挺住
    Cielsky
        17
    Cielsky  
       2020-12-07 12:50:00 +08:00 via Android
    一条线段的起点地址加上线段长度的一半不就是中间位置的地址吗😂
    redtea
        18
    redtea  
       2020-12-07 12:51:15 +08:00
    int mid = (low + high) >>> 1;
    yy77
        19
    yy77  
       2020-12-07 12:53:50 +08:00
    即使 high low 都在数据类型的范围内,但是 low + high 就可能溢出。用 int mid = low + (high - low)/2 就能避免溢出。
    Mutoo
        20
    Mutoo  
       2020-12-07 12:56:46 +08:00   ❤️ 1
    证:
    (low + high) / 2 =
    low / 2 + high / 2 =
    (low - low / 2) + high / 2 =
    low + (high - low) / 2

    证毕
    ccvzz
        21
    ccvzz  
       2020-12-07 15:25:58 +08:00 via Android
    @Mutoo 然而你的证明是错的。整数除法的话,你第一个等式就不对。let low=1,high=3,(low+high)/2=2,low/2+high/2=0+1=1
    lrlz
        22
    lrlz  
       2020-12-07 16:16:19 +08:00
    夹逼准则
    LGA1150
        23
    LGA1150  
       2020-12-07 17:18:37 +08:00
    @redtea #18
    负数下溢出会出问题
    (Integer.MIN_VALUE * 2) >>> 1 会变成 0
    redtea
        24
    redtea  
       2020-12-07 17:56:13 +08:00
    @LGA1150 int mid = low + ((high - low)>>1);
    hello2060
        25
    hello2060  
       2020-12-07 18:04:58 +08:00 via iPhone
    @ccvzz 不只整数乘法,他这浮点数也不对啊。
    Raven316
        26
    Raven316  
       2020-12-07 18:09:43 +08:00
    小学毕业了吗
    AmosAlbert
        27
    AmosAlbert  
       2020-12-07 18:21:58 +08:00
    suikatw
        28
    suikatw  
       2020-12-07 18:35:15 +08:00
    @linauror 为什么这么写就可以防止溢出呢? high-low 感觉还是会溢出吧,比如 high = -INT_MAX, low=INT_MAX
    venster
        29
    venster  
       2020-12-07 18:47:20 +08:00 via iPhone
    @imn1 看了这么多就没几个靠谱的,就你解释的最简洁明了了。
    hello2060
        30
    hello2060  
       2020-12-07 18:51:07 +08:00
    @suikatw 同学,这是在说 2 分法写程序哇,left > right 的情况早就函数退出了啊
    Ehend
        31
    Ehend  
       2020-12-07 19:02:24 +08:00
    。。。low+(high-low)/2,第一个 low 你理解为起点的偏移量就行,后面的部分就是取 1/2
    suikatw
        32
    suikatw  
       2020-12-07 19:11:11 +08:00
    @hello2060 还是不懂,那改一下,high=INT_MAX, low=-INT_MAX 。int mid = low + (high - low)/2; 计算这条语句的时候算到括号里 high-low 不就溢出了么?
    suikatw
        33
    suikatw  
       2020-12-07 19:13:01 +08:00
    @imn1 为什么会考虑 h+l 溢出但是不考虑 h-l 溢出呢?
    hello2060
        34
    hello2060  
       2020-12-07 19:19:39 +08:00
    @suikatw 好吧,那就真的溢出了。你是对的。

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

    high=INT_MAX, low=-INT_MAX 那肯定还是溢出了
    Ehend
        35
    Ehend  
       2020-12-07 19:20:49 +08:00
    @suikatw 额,二分查找工程里用的话,哪有序号是负数的。。。即使从 0 开始计数,INT_MAX-0=INT_MAX,这不是还是没溢出吗。。。
    suikatw
        36
    suikatw  
       2020-12-07 19:28:41 +08:00
    是我忽略了数组下标取值这个前提场景,确实可以防止溢出
    wzcloud
        37
    wzcloud  
       2020-12-07 19:48:04 +08:00
    数学中的公式。。。
    mid=(low+high)/2=(low+high+low-low)/2=(2low+high-low)/2=low+(high-low)/2
    jimmyismagic
        38
    jimmyismagic  
       2020-12-07 19:52:22 +08:00
    我发现越简单的问题,讨论得越多,越没有价值的会,开得越长
    flippydoo
        39
    flippydoo  
       2020-12-07 20:03:20 +08:00
    义务教育的普及有待提高
    lxilu
        40
    lxilu  
       2020-12-08 00:19:03 +08:00 via iPhone   ❤️ 1
    @hello2060 @ccvzz,@Mutoo 明明是数学证明
    hello2060
        41
    hello2060  
       2020-12-08 07:42:04 +08:00
    @lxilu 哈哈 我是故意逗他的嘿嘿
    zhongrs232
        42
    zhongrs232  
       2020-12-10 16:57:19 +08:00
    mark 一下,今天刷题写了个二分查找,写完总感觉哪里不对,似乎在 V 站上看到有人提过相关的问题,搜索了一下果然有,感谢 V2EX 让我知道(low+high)/2 的写法有溢出风险,哈哈哈哈。另外,V 站的 google 收录效果好高,三天前的帖子,用关键字“二分查找 mid = low + (high - low) / 2”搜索,第三条就是这个帖子。
    charlie21
        43
    charlie21  
       2020-12-19 22:07:41 +08:00
    已知 low,求 mid:
    mid = low + low 到 mid 的距离,解决。这样可以少考虑一个变量( high )
    关于   ·   帮助文档   ·   API   ·   FAQ   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   2814 人在线   最高记录 5497   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 29ms · UTC 13:02 · PVG 21:02 · LAX 06:02 · JFK 09:02
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.