對于陣列中的分治演算法，我們需要能夠找到范圍的中間元素。這樣做的明顯方法是mid = (leftSide rightSide) / 2。但是，我聽說這種方式是不正確的，我們需要改寫mid = leftSide (rightSide - leftSide) / 2。有人可以解釋這兩者之間的區別嗎？
uj5u.com熱心網友回復：
使用(leftSide rightSide) /2可以溢位，根據不同的語言和你正在使用的資料型別的值leftSide和rightSide。原因是，你先加leftSide和rightSide，然后除以2，它們。
在此方法中，leftSide (rightSide - leftSide)/2您將它們減去并除以 2，然后添加 leftSide，這在某些情況下會有所不同。
除此之外，這些運算式在數學上是相同的，如下所示：
leftSide (rightSide - leftSide)/2
2leftSide/2 (rightSide - leftSide)/2
(2leftSide rightSide - leftSide)/2
(rightSide leftSide)/2
根據 OP 的要求，我添加了一個關于如何(leftSide rightSide) / 2溢位的具體 Java 示例。
假設我們在 java中存盤left和right，int它們是 4 位元組有符號整數。這意味著它們覆寫-2^31到2^31-1。現在，進一步假設我們有0和2147483000作為我們的左右。請記住，我們的上限僅略小于 4 位元組有符號整數的上限2^31-1 = 2147483647。第一次搜索后，由于目標位于右側，左側變為1073741501，因為2147483000 / 2 1 = 1073741501。現在使用該公式(left right) / 2是危險的。因為：
left = 2147483000 / 2 1 = 1073741501
right = 2147483000
left right = 3221224501
因此，left right高于無符號 4 位元組整數的可用限制/位。發生的情況是 Java 將新整數解釋為負數，因為設定了顯示符號的最高有效位。考慮以下示例：
public class Main
{
public static void main(String[] args) {
int right = 2147483647;
int left = 1073741500;
System.out.println(left " " right);
System.out.println(left right);
}
}
輸出：
1073741500 2147483647
-1073742149
長話短說，您可以通過使用leftSide (rightSide - leftSide)/2. 由于您先從右減去左，然后再除以 2，因此不存在溢位的風險。
如果您有興趣，請閱讀Google 研究工程師的博客文章，介紹二分搜索中此錯誤的普遍程度。
uj5u.com熱心網友回復：
請注意，對于所有L和R，
(L R) / 2 = (2.L - L R) / 2 = L (R - L) / 2.
使用整數演算法。因此沒有區別（溢位或負數的情況除外；那么即使除以 2 或右移也可能產生不同的結果）。
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/369679.html