溢出漏洞

这篇文章就来聊一聊关于归并排序与二分查找的溢出漏洞。这个漏洞并没有多么神奇，其实很好理解，可能由于是所有人都没往这方面想，所以20多年都没被发现。

首先，关键点我都在前几篇文章里打了注释，其实就这一句话

1	int mid=(left+right)/2;

为什么这句话会带来溢出呢，这就要说到int的上限的问题了，int的最大值是2^31，那么，我们可以假设一下我们有一个长度为2^31的数组，然后我们要在其中搜索一个数字，这个数字还碰巧是在很后面的（接近2^31的位置），那么我们来模拟一下这个过程。

所以这下知道为什么mid=(left+right)/2这句话带来巨大的问题了吧。如果int一旦溢出，很可能left+right就会变成负数，随之而来的就是很可能程序访问数组也是用的负数，然后你的程序莫名其妙就炸了。

所以我们该如何解决这个问题呢，一共有两种办法。

第一种方法（采用无符号int——unsigned int）

既然我们的数组没有下标为负数的，那我们不如采用不加符号位的int来扩大传统int的范围，这样当你使用的数据为int时就不会爆了。

1	int mid=((unsigned int)left+(unsigned int)right)/2;

或者我们使用右移运算符。

1	int mid=((unsigned int)left+(unsigned int)right)>>1;

当然，java中有一个更简便的，叫做无符号右移’>>>’，直接包含了unsigned int和右移的功能，我们在java中也可以使用它来解决。

1	int mid=(left+right)>>>1;

我们想求出mid当然不止这一种直接增加的方法，我们可以采用先将left和right的距离的一半算出来，然后left的位置加上这一半的距离自然就是mid的位置了，所以，也可以用下面这种。

1	int mid=left+(right-left)/2;

这样自然就不会出现溢出了（大家可以自己模拟一下看看溢出了没有），这种方法相对来讲更加数学式，更加灵性，不需要扩大范围，我个人还是更喜欢这种方法的。

ok，那关于溢出漏洞就说到这。