0

尝试对 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;
4

4 回答 4

4

给你几个建议：

  • 无需保留Book变量。在你的循环中，只要找到这本书就返回它，最后返回null。您还可以删除条件中变量的布尔检查while。

  • 变量可以在middle循环内限定范围，不需要让它活得更久。

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

  • 这middle = (bottom + top)/2是二进制搜索实现算法中的一个典型错误。甚至编写 Java Collection 类的 Joshua Bloch 也犯了这个错误（请参阅这篇有趣的博客文章）。相反，使用(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-27T12:08:34.383 回答
2

Collections.binarySearch() 呢？

于 2010-02-27T11:43:48.823 回答
0

JRL 的所有建议都是正确的，但实际失败是您的比较被颠倒了。

我自己并没有立即看到这一点，但是将您的代码复制到一个函数中（使用字符串而不是 Books），编写一些简单的 Junit 测试然后在调试器中运行它们就非常明显了。

编写单元测试！

于 2010-02-27T12:37:11.587 回答
0

我发现了问题。

事实证明，我正在对我的 bookCollection arrayList 进行二进制搜索，而不是我创建的新 sroted 数组 - sortedLib。

我最后犯了一个愚蠢的错误，但感谢您的意见和建议！

于 2010-02-28T12:25:36.327 回答