为什么这个二进制搜索执行导致溢出

Question

在二进制搜索的执行

int search(int[] A, int K) { 
    int l = 0; 
    int u = A.length - 1; 
    int m 
    while (l <= u) { 
    m = (l+u)/2; // why this can cause overflow 
    ... 
    } 
} 

正确的方法如下：

m = l + (u -l)/2; 

我不知道为什么更新语句没有溢出问题。根据我的理解， 不久或更晚，更新后的语句也会有溢出问题。

谢谢

Answer 1

的一部开拓创新的可能溢出，因为l+u可能比一个int可以处理的最大值（例如，如果两个l和u是INT_MAX那么它们的和将明显超过INT_MAX）更大。

正确的方法不能溢出，因为u-l显然不会溢出，并且l+(u-l)/2保证是<=u，所以也不能溢出。