Java二分查找

Question

尝试对 Book 对象的排序数组执行二分搜索。

它工作得不好，它返回了某些对象的正确结果，但不是全部。

我在纸上完成了循环，似乎由于向上舍入 #.5 可能会遗漏一个数字。

有什么想法可以让这项工作发挥作用吗？

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;

Answer 1

给您一些建议:

• 没有必要保留 Book多变的。在您的循环中，只需在找到该书时将其归还，最后返回 null 。您还可以删除 while 中变量的 boolean 检查。情况。

• middle变量可以在循环内限定作用域，无需让它存在更长时间。

• 你在做什么bookCollection.get(middle).getReference()三次。考虑创建一个变量然后使用它。

• middle = (bottom + top)/2是二分搜索实现算法中的一个经典错误。甚至 Java Collection 类的编写者 Joshua Bloch 也犯了这个错误(请参阅 this interesting blog post 来了解它)。相反，使用 (bottom+top) >>> 1 ，以避免非常大的值的整数溢出(您可能不会遇到此错误，但这是原则性的)。

对于您的实际问题陈述，四舍五入将向下(整数除法)，而不是向上。解决问题的方法:

• 您确定是 numberOfBooks()方法对应于您的集合的长度？
• 您确定是 compareTo()方法按您所使用的类型的预期工作(在您的代码示例中，我们不知道 getReference() 返回类型是什么)
• 您确定您的 Collection 已按照 getReference() 正确排序吗？ ？
• 最后，您确定使用 givenRef.compareTo(bookCollection.get(middle).getReference()) < 0是正确的？在标准的二分搜索实现中，它会被颠倒，例如bookCollection.get(middle).getReference().compareTo(givenRef) < 0 。这可能是donroby提到的，不确定。

无论如何，找到错误的方法是尝试不同的值，看看哪些输出正确，哪些不正确，从而推断出问题所在。如果您必须运行许多测试，您还可以使用调试器来帮助您逐步完成算法，而不是使用铅笔和纸。更好的是，正如 Donroby 所说，编写一个单元测试。