疑问

王老师，每次听你的课有一种醍醐灌顶的感觉。

昨天上课的时候，你讲到分治法的时候，有个例子，在P98页算法例4.11 合并排序的分治算法。有一些疑问。

疑问

算法4.11代码如下：

template <class Type>
void mergesort(Type A[],int low,int high)
{
 int mid;
 if(low<high){
 mid = (low+high)/2;//昨天你在PPT上面是(high-low)/2
 mergesort(A,low,mid);
 mergesort(A,mid+1,high)
 merge(A,low,mid,high);
}
}

这里的疑问你在于 昨天你说求数组的中间元素两种方法是一样的。你的证明如下：

(low+high)/2-(high-low)/2=low

我感觉这里你理解错了 low的含义了，low应该是一个未知的变量，不是你所说的0；
另外我在查找资料后，发现应该是这样写的。

(low+high)/2=(high-low)/2+low

这里说明了寻找数组的中间元素有两种方法，但是在资料中显示这样一段话

int binary_search(int arrSeq[], int nLength, int nKey)  
{  
if (arrSeq == NULL || nLength<1)  
{  
return -1;//不合法  
}  
else if (nKey<arrSeq[0] || nKey>arrSeq[nLength - 1])  
{  
return -1;//不合法  
}  
int low = 0;  
int high = nLength - 1;  
while (low <= high)  
{  
int middle = (high - low) / 2 + low; // 直接使用(high + low) / 2 可能导致溢出  
if (arrSeq[middle] == nKey)  
return middle;  
//在左半边  
else if (arrSeq[middle] > nKey)  
high = middle - 1;  
//在右半边  
else  
low = middle + 1;  
}  
//没找到  
return -1;  
}  

问题

**直接使用(high + low) / 2 可能导致溢出 **
这里有很大的疑问，为什么会有这种区别，都是定义的整型变量，而且基本上这句话的时间复杂度都是1，为什么使用（high+low)/2会出现栈溢出，这是案例http://www.magicsite.cn/blog/Java/Java/Java237595.html。希望王老师给出一些资料，让我去找一下