Java二進制搜索

嘗試在已排序的Book對象數組上執行二分搜索。Java二進制搜索

它工作不正常，它返回一些對象的正確結果，但不是全部。

我經歷了紙上的循環，似乎由於向上舍入數字可能會錯過一個數字。

任何想法如何使這項工作？

Book found = null; 
    /* 
    * Search at the center of the collection. If the reference is less than that, 
    * search in the upper half of the collection, else, search in the lower half. 
    * Loop until found else return null. 
    */ 
    int top = numberOfBooks()-1; 
    int bottom = 0; 
    int middle; 
    while (bottom <= top && found == null){ 
     middle = (bottom + top)/2; 
     if (givenRef.compareTo(bookCollection.get(middle).getReference()) == 0) { 
      found = bookCollection.get(middle); 
     } else if (givenRef.compareTo(bookCollection.get(middle).getReference()) < 0){ 
      bottom = middle + 1; 
     } else if (givenRef.compareTo(bookCollection.get(middle).getReference()) > 0){ 
      top = middle - 1; 
     } 
    } 
    return found;

來源

2010-02-27 user195257

這是功課嗎？ – PSpeed 2010-02-27 11:24:44

我將它添加到一門課程中。只需要一個標準的搜索，但我想包括一個二進制搜索，以使其從人羣中脫穎而出 – user195257 2010-02-27 11:29:10

Collections.binarySearch（）怎麼樣？

來源

2010-02-27 11:43:48 3biga

我想自己寫一個方法。謝謝 – user195257 2010-02-27 11:57:01

@user ...你爲什麼要這麼做？家庭作業？ – whiskeysierra 2010-02-27 16:31:18

自己實現算法是瞭解算法的好方法。在生產代碼中，使用語言或庫中提供的實現當然是一個好主意。 – 2010-02-27 17:02:12

爲您一對夫婦建議：

沒有必要保持Book變量。在你的循環中，只要在找到該書時將其歸還，最後返回null。您還可以刪除while條件中變量的布爾檢查。
middle變量可以在循環內部作用域，不需要讓它活得更長。
你正在做bookCollection.get(middle).getReference()三次。考慮創建一個變量然後使用它。
middle = (bottom + top)/2是二進制搜索實現算法的經典錯誤。甚至編寫Java Collection類的Joshua Bloch也犯了這個錯誤（參見this interesting blog post）。相反，使用(bottom+top) >>> 1，以避免整數溢出非常大的值（你可能不會遇到這個錯誤，但它的原則）。

至於你的實際問題陳述，舍入將向下（整數除法），而不是向上。要排查問題：

您確定numberOfBooks()方法對應於您的收藏的長度？
你確定了compareTo()方法按預期工作對於正在使用
。您確定要收集正確根據getReference()排序的類型（在你的代碼示例中，我們不知道getReference()返回類型是什麼）？
最後，你確定使用givenRef.compareTo(bookCollection.get(middle).getReference()) < 0是正確的嗎？在標準的二進制搜索實現中，它將被顛倒，例如， bookCollection.get(middle).getReference().compareTo(givenRef) < 0。這可能是donroby提到的，不確定。

在任何情況下，找到錯誤的方法是嘗試不同的值並查看哪些輸出是正確的，哪些不正確，從而推斷出問題所在。您還可以使用調試器幫助您逐步完成算法，而不必使用鉛筆和紙張，如果必須運行多個測試。更好的是，正如donroby所說，寫一個單元測試。

來源

2010-02-27 12:08:34 JRL

我確定它會返回集合的大小，任何其他想法爲什麼它不會一致工作？ – user195257 2010-02-27 12:30:49

+1（底部+頂部）>>> 1 – whiskeysierra 2010-02-27 16:32:17

JRL的所有建議都是正確的，但實際失敗在於您的比較是顛倒的。

我沒有立即看到這個，但是將你的代碼複製到一個函數中（使用字符串而不是Books），編寫一些簡單的Junit測試，然後在調試器中運行它們，這非常明顯。

編寫單元測試！

來源

2010-02-27 12:37:11

謝謝，但扭轉我的比較沒有工作？ – user195257 2010-02-27 12:42:28

瞭解發生了什麼的另一個策略是調試打印。我建議在循環中放入一些中間元素或索引的打印內容，看看是否能夠讓你知道哪裏出錯。這或多或少是我在調試器中看到的... 通過比較反轉和其他更改，它似乎對字符串正常工作。我能想到的唯一的另一件事是，如果列表實際上沒有排序，這肯定會失敗，無法預料。 – 2010-02-27 13:11:22

我發現了這個問題。

原來我是二進制搜索我的bookCollection arrayList，而不是我創建的新sroted數組 - sortedLib。

愚蠢的錯誤在我的結尾，但感謝您的意見和建議！

來源

2010-02-28 12:25:36 user195257

Java二進制搜索

回答

相關問題