爲什麼這個二進制搜索執行導致溢出

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，所以也不能溢出。