java 中二分查找取中间值的这个公式,是数学中的什么公式啊?我知道这样写是为了防止数值溢出,int mid = low + (high - low)/2; 但是我想知道这个是数学里面的什么公式? 正常来说求中间值不就是最大数 + 最小数 再除以 2 = 中间数。比如 1 和 9 。1 + 9 = 10 10 /2=5,5 刚好就是中间数,但是这个公式我搞不懂 int mid = low + (high - low)/2;
1
linauror 2020-12-07 10:49:13 +08:00 3
防止溢出的求中间值写法
|
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 就溢出了 |
3
zxCoder 2020-12-07 10:51:25 +08:00
画个图看看,一个短线和一个长线的平均数,不就是等于短线加上他俩中间相差部分的一半?
|
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
|
5
abelmakihara 2020-12-07 10:53:24 +08:00
你都知道是为了防止数值溢出的了
不考虑这个 low + (high - low)/2 不就等价于(high+low)/2 吗 |
6
hello2060 2020-12-07 10:54:53 +08:00 1
同学 (a + b) /2 不就是 a + (b - a) /2 吗 ?
(b - a) /2 就是 ab 间距离的一半,从 a 开始走这一半,不就到 ab 中间点了吗? |
7
imn1 2020-12-07 10:57:15 +08:00 1
数学理论是一样的
计算机这样写,是因为 h 和 l 都没有溢出,但 h+l 有可能溢出了,l+(h-l)/2 能确保不会溢出 |
8
jdhao 2020-12-07 10:57:17 +08:00 via Android
这都水一贴。。
|
10
Kasumi20 2020-12-07 11:21:58 +08:00
上 BigInteger 就可以
|
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/
|
12
dswyzx 2020-12-07 12:09:33 +08:00
除法展开.是义务教育的范畴吧
|
13
PopRain 2020-12-07 12:33:13 +08:00
小学生都会的推导过程。。。。。
|
14
BBCCBB 2020-12-07 12:35:32 +08:00
....楼主你...
|
15
violence123456 2020-12-07 12:38:10 +08:00 via iPhone
你这数学功底太感人了吧,low+( high-low )/2 不就等于( low+high )/2 ?😂
|
16
wshwwl 2020-12-07 12:47:52 +08:00 via iPhone 5
这样的也能编程,我对自己的肯定又多了一分,挺住
|
17
Cielsky 2020-12-07 12:50:00 +08:00 via Android
一条线段的起点地址加上线段长度的一半不就是中间位置的地址吗😂
|
18
redtea 2020-12-07 12:51:15 +08:00
int mid = (low + high) >>> 1;
|
19
yy77 2020-12-07 12:53:50 +08:00
即使 high low 都在数据类型的范围内,但是 low + high 就可能溢出。用 int mid = low + (high - low)/2 就能避免溢出。
|
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 证毕 |
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
|
22
lrlz 2020-12-07 16:16:19 +08:00
夹逼准则
|
26
Raven316 2020-12-07 18:09:43 +08:00
小学毕业了吗
|
27
AmosAlbert 2020-12-07 18:21:58 +08:00
|
28
suikatw 2020-12-07 18:35:15 +08:00
@linauror 为什么这么写就可以防止溢出呢? high-low 感觉还是会溢出吧,比如 high = -INT_MAX, low=INT_MAX
|
31
Ehend 2020-12-07 19:02:24 +08:00
。。。low+(high-low)/2,第一个 low 你理解为起点的偏移量就行,后面的部分就是取 1/2
|
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 不就溢出了么?
|
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 那肯定还是溢出了 |
35
Ehend 2020-12-07 19:20:49 +08:00
@suikatw 额,二分查找工程里用的话,哪有序号是负数的。。。即使从 0 开始计数,INT_MAX-0=INT_MAX,这不是还是没溢出吗。。。
|
36
suikatw 2020-12-07 19:28:41 +08:00
是我忽略了数组下标取值这个前提场景,确实可以防止溢出
|
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 |
38
jimmyismagic 2020-12-07 19:52:22 +08:00
我发现越简单的问题,讨论得越多,越没有价值的会,开得越长
|
39
flippydoo 2020-12-07 20:03:20 +08:00
义务教育的普及有待提高
|
42
zhongrs232 2020-12-10 16:57:19 +08:00
mark 一下,今天刷题写了个二分查找,写完总感觉哪里不对,似乎在 V 站上看到有人提过相关的问题,搜索了一下果然有,感谢 V2EX 让我知道(low+high)/2 的写法有溢出风险,哈哈哈哈。另外,V 站的 google 收录效果好高,三天前的帖子,用关键字“二分查找 mid = low + (high - low) / 2”搜索,第三条就是这个帖子。
|
43
charlie21 2020-12-19 22:07:41 +08:00
已知 low,求 mid:
mid = low + low 到 mid 的距离,解决。这样可以少考虑一个变量( high ) |