java 中二分查找取中间值的这个公式，是数学中的什么公式啊？我知道这样写是为了防止数值溢出，int mid = low + (high - low)/2; 但是我想知道这个是数学里面的什么公式？ 正常来说求中间值不就是最大数 + 最小数 再除以 2 = 中间数。比如 1 和 9 。1 + 9 = 10 10 /2=5，5 刚好就是中间数,但是这个公式我搞不懂 int mid = low + (high - low)/2;
Java 中二分查找取中间值的这个公式 int mid = low + (high - low)/2;，是数学中的什么公式啊？这个是什么原理啊？
burnbrid · Dec 7, 2020 · 7209 viewsThis topic created in 2161 days ago, the information mentioned may be changed or developed.
 |
1
防止溢出的求中间值写法
|
3 |
2
比如：int max = INT_MAX
int low = max - 2 int high = max - 1 如果直接求 mid，high+low 就溢出了 |
 |
zxCoderDec 7, 2020
3
画个图看看，一个短线和一个长线的平均数，不就是等于短线加上他俩中间相差部分的一半？
|
 |
morrieatiDec 7, 2020
4
一样的，low + (high - low) / 2 == low + high / 2 - low / 2 == high / 2 + low / 2 == (high + low) / 2
|
 |
BornThisWayDec 7, 2020
5
你都知道是为了防止数值溢出的了
不考虑这个 low + (high - low)/2 不就等价于(high+low)/2 吗 |
 |
6
同学 (a + b) /2 不就是 a + (b - a) /2 吗 ？
(b - a) /2 就是 ab 间距离的一半，从 a 开始走这一半，不就到 ab 中间点了吗？ |
 |
7
数学理论是一样的
计算机这样写，是因为 h 和 l 都没有溢出，但 h+l 有可能溢出了，l+(h-l)/2 能确保不会溢出 |
 |
jdhaoDec 7, 2020 via Android
8
这都水一贴。。
|
 |
Kasumi20Dec 7, 2020
10
上 BigInteger 就可以
|
|
11
@jdhao java 官方的二分搜索之前也有这个 bug，没考虑溢出，后面被修复了。之前做 leetcode 也遇到过这个问题 https://jdhao.github.io/2017/08/27/binary-search-overflow-issue/
|
 |
dswyzxDec 7, 2020
12
除法展开.是义务教育的范畴吧
|
 |
PopRainDec 7, 2020
13
小学生都会的推导过程。。。。。
|
 |
BBCCBBDec 7, 2020
14
....楼主你...
|
 |
violence123456Dec 7, 2020 via iPhone
15
你这数学功底太感人了吧，low+（ high-low ）/2 不就等于（ low+high ）/2 ？😂
|
 |
16
这样的也能编程，我对自己的肯定又多了一分，挺住
|
 |
CielskyDec 7, 2020 via Android
17
一条线段的起点地址加上线段长度的一半不就是中间位置的地址吗😂
|
 |
redteaDec 7, 2020
18
int mid = (low + high) >>> 1;
|
 |
yy77Dec 7, 2020
19
即使 high low 都在数据类型的范围内，但是 low + high 就可能溢出。用 int mid = low + (high - low)/2 就能避免溢出。
|
 |
20
证：
(low + high) / 2 = low / 2 + high / 2 = (low - low / 2) + high / 2 = low + (high - low) / 2 证毕 |
 |
0xoDec 7, 2020 via Android
21
@Mutoo 然而你的证明是错的。整数除法的话，你第一个等式就不对。let low=1，high=3，(low+high)/2=2，low/2+high/2=0+1=1
|
 |
lrlzDec 7, 2020
22
夹逼准则
|
 |
Raven316Dec 7, 2020
26
小学毕业了吗
|
 |
AmosAlbertDec 7, 2020
27
 |
 |
EhendDec 7, 2020
31
。。。low+(high-low)/2，第一个 low 你理解为起点的偏移量就行，后面的部分就是取 1/2
|
 |
suikatwDec 7, 2020
32
@hello2060 还是不懂，那改一下，high=INT_MAX, low=-INT_MAX 。int mid = low + (high - low)/2; 计算这条语句的时候算到括号里 high-low 不就溢出了么？
|
|
hello2060Dec 7, 2020
34
@suikatw 好吧，那就真的溢出了。你是对的。
但是二分法一般用在数组查找啊，left，right 起始值一般是 0 和 array.length - 1 啦，所以 right - low <= INT_MAX high=INT_MAX, low=-INT_MAX 那肯定还是溢出了 |
|
suikatwDec 7, 2020
36
是我忽略了数组下标取值这个前提场景，确实可以防止溢出
|
 |
wzcloudDec 7, 2020
37
数学中的公式。。。
mid=(low+high)/2=(low+high+low-low)/2=(2low+high-low)/2=low+(high-low)/2 |
 |
jimmyismagicDec 7, 2020
38
我发现越简单的问题，讨论得越多，越没有价值的会，开得越长
|
 |
flippydooDec 7, 2020
39
义务教育的普及有待提高
|
 |
zhongrs232Dec 10, 2020
42
mark 一下，今天刷题写了个二分查找，写完总感觉哪里不对，似乎在 V 站上看到有人提过相关的问题，搜索了一下果然有，感谢 V2EX 让我知道(low+high)/2 的写法有溢出风险，哈哈哈哈。另外，V 站的 google 收录效果好高，三天前的帖子，用关键字“二分查找 mid = low + (high - low) / 2”搜索，第三条就是这个帖子。
|
 |
charlie21Dec 19, 2020
43
已知 low，求 mid：
mid = low + low 到 mid 的距离，解决。这样可以少考虑一个变量（ high ） |
Select Language