今天leetcode刷题时,发现个求平均数的溢出陷阱。
正常人用以下方法求平均数:
int left, right; // left > 0, right >0
int mid = (left +right) /2;
这里面隐藏的陷阱就是这个(left +right)
的值可能会超过Integer.MAX_VALUE
造成错误。
那么就必须用下面这个办法:
int left, right; // left > 0, right >0
int mid = (right - left)/2 + left;
易得,以上两种求法等价,但是(在left > 0, right >0
的前提下)后者不会溢出