修復賓利書籍（編程珍珠：編寫正確的程序）中的二進制搜索錯誤

二進制搜索可以通過多種方式實現 - 遞歸，迭代，條件等。我從賓利的書「編程珍珠：編寫正確的程序「這是一個迭代實現，並且包含一個bug。修復賓利書籍（編程珍珠：編寫正確的程序）中的二進制搜索錯誤

public class BinSearch 
    { 
     static int search(int [] A, int K) { 
      int l = 0; 
      int u = A. length -1; 
      int m; 
      while (l <= u) { 
       m = (l+u) /2; 
       if (A[m] < K){ 
       l = m + 1; 
       } else if (A[m] == K){ 
        return m; 
       } else { 
        u = m-1; 
       } 
     } 
    return -1; 
    } 
}

我在行m =（l + u）/ 2中發現了一個錯誤;它可能導致溢出。我們如何避免這種二分查找中的溢出？

來源

2013-06-28 Jayram Singh

而不是'while（l <= U）'是'while（l <= u）'而不是？ – Machtl

我從書中拿...編程珍珠：寫出正確的程序。 –

'U'將是未知的標識符，'u'更有意義。你有沒有試圖編譯它？ – Machtl

嘗試以下操作：

變化，如果你認爲一個非常大的陣列的2

m = (l+u) /2

到

m = (u-l)/2 + l

爲什麼(l+u)/2可能溢出的原因是顯而易見的^ 31 - 1個元素（最大值是一個有符號的32位整數）。在這種情況下，第一次迭代就沒有問題，因爲2^31 - 1 + 0不是什麼大問題，但在這裏考慮一下l = m + 1的情況。在第二次迭代中，u仍然相同，並且l是2^31/2，因此l + u將導致溢出。

這樣我們就避免了u + l的增加，方法是首先確定l和u之間的相對中間值，然後將較小的數字l加到它上面，這樣就變成了絕對值。所以在操作m = (u-l)/2 + l;期間，我們永遠不會超過u的價值。

總結的完整代碼：

public class BinSearch 
{ 
    static int search(int [] A, int K) 
    { 
     int l = 0; 
     int u = A. length -1; 
     int m; 

     while (l <= u) 
     { 
      m = (u-l)/2 + l; 

      if (A[m] < K) 
       l = m + 1; 
      else if (A[m] == K) 
       return m; 
      else 
       u = m - 1; 
     } 
     return -1; 
    } 
}

來源

2013-07-07 06:49:07 Machtl

從技術上講，這個問題可能發生在一個數組上，其中'2^30（+1？）'和'2^31-1'元素之間的任何地方。 – Dukeling

我想你應該改變U = M-L;到u = m -1。

它是1不是l。 --------- addtion ------ 因爲（l + u）可能大於2^31-1（如果int是32bits），所以可能溢出。所以你應該改變（l + u）/ 2到l +（（u-1）>> 1），並且u-1不能大於2^31-1。

來源

2013-07-07 07:02:44

是啊:)已更改 –

嘗試改變

m = (l+u)/2

到

m = l + (u - l)/2

這是微不足道的看到，無論是相等的，也是第二個語句防止溢出。

來源

2013-07-07 07:43:02 Ayberk

假設l和u都是int都落入[0，2^31-1]。如果l，u> = 2^30，則（l + u）> = 2^31溢出。爲避免這種情況，請使用

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

改爲。更重要的是，它可能是更合理的寫二進制搜索是這樣的：

public class BinSearch 
    { 
     static int search(int [] A, int K) { 
      int l = -1;    // index lower bound shift left by 1 
      int u = A.length;  // index upper bound shift right by 1 
      int m; 
      while (l + 1 < u) { 
       m = l + (u-l)/2; // avoid overflow 
       if (A[m] < K){ 
        l = m;   // keep A[l] < K 
       } else { 
        u = m;   // keep A[u] >= K 
       } 
      } 
      if ((u == A.length) || (A[u] != K)) return -1; 
      return u; 
     } 
    }

來源

2013-07-08 13:16:33 frankyym

正如一些人所說，該修補程序很簡單，當然我已經看到了100點賞金最簡單的！這裏是另一個，它有一個很好的對稱性，即使這需要一些更多的時鐘週期：

m = (l >> 1) + (u >> 1) + (l & u & 1);

你不應該詆譭賓利「一個錯誤」，直到你有更好的信息。當他爲ACM寫這篇文章時（我想是在1980年代的某個時候），他用32位C進行僞編碼和寫作;有千兆字節RAM的機器不存在。即使他們有4個字節的整數，一個32位的機器也不能有超過2^28個整數的數組。因此最高可能的指數是2^28-1。加倍這個值而不是導致int溢出。

當然，它與32位Java完全一樣。您需要64位Java的破碎的kludge - 一種允許大小接近2^64的對象的語言，但將索引限制爲2^32-1以便導致出現這個「錯誤」。

你稱之爲錯誤的是操作假設的改變。如果環境以正確的方式改變，宇宙中的每一個程序都會表現出某種缺陷。

來源

2013-07-09 21:09:18 Gene

本書的讀者將包括使用16位整數的嵌入式設備的編碼器。我會把它稱爲一個錯誤，特別是因爲它處於說明性的形式。我懷疑賓利也會。 –

迭代實現二進制搜索確實有一個錯誤。更改m = (l+u)/2。正如其他人所說，它可能導致整數溢出。用m = l + (u-l)/2代替。

根據經驗，我有一次又一次看到越野車二進制搜索實現。二元搜索雖然涉及分而治之的簡單概念很難得到正確。它很容易改變上面的m作業。希望這有助於...

來源

2013-07-12 15:48:02

爲什麼不「m = 1/2 + u/2」？這也可以防止溢出，不是嗎？但是，分割操作執行兩次。你說什麼？ – kunal18

@stalin考慮L和U都是奇數的情況。 – netanelw

@netanelw：是的，我沒有想到這一點。謝謝！ – kunal18

雖然Machtl和其他人已經寫入克服溢出錯誤的方式，但加入只是爲了完整起見

使用INT中旬=（低+高）>> > 1;更快的方式
而在C和C++（我們沒有>>>運算符） mid =（（unsigned int）low +（unsigned int）high））>> 1;

來源

2014-01-01 05:41:58 Prakhar

修復賓利書籍（編程珍珠：編寫正確的程序）中的二進制搜索錯誤

回答

相關問題