Java二分查找
尝试对 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;
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（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())givenRef.compareTo(bookCollection.get(middle).getReference()) < 0是正确的吗？在标准的二分搜索实现中，它会被颠倒，例如bookCollection.get(middle).getReference().compareTo(givenRef)bookCollection.get(middle).getReference().compareTo(givenRef) < 0 。这可能是唐罗比提到的，不确定。无论如何，找到错误的方法是尝试不同的值，看看哪些输出正确，哪些输出不正确，从而推断出问题所在。如果您必须运行许多测试，您还可以使用调试器来帮助您逐步完成算法，而不是使用铅笔和纸。更好的是，正如 Donroby 所说，编写一个单元测试。
A couple suggestions for you:
there's no need to keep a
Bookvariable. In your loop, just return the book when it's found, and at the end returnnull. And you can also remove the boolean check for the variable in thewhilecondition.the
middlevariable can be scoped inside the loop, no need to have it live longer.you're doing
bookCollection.get(middle).getReference()three times. Consider creating a variable and then using it.the
middle = (bottom + top)/2is a classic mistake in binary search implementation algorithms. Even Joshua Bloch, who wrote the Java Collection classes, made that error (see this interesting blog post about it). Instead, use(bottom+top) >>> 1, to avoid integer overflow for very large values (you probably wouldn't encounter this error, but it's for the principle).As for your actual problem statement, rounding would be downwards (integer division), not upwards. To troubleshoot the problem:
numberOfBooks()method corresponds to the length of your collection?compareTo()method works as expected for the types you are using (in your code example we do not know what thegetReference()return type is)getReference()?givenRef.compareTo(bookCollection.get(middle).getReference()) < 0is correct? In standard binary search implementations it would be reversed, e.g.bookCollection.get(middle).getReference().compareTo(givenRef) < 0. This might be what donroby mentions, not sure.In any case, the way to find the error would be to try out different values and see for which the output is correct and for which it isn't, and thus infer what the problem is. You can also use your debugger to help you step through the algorithm, rather than using pencil and paper if you have to run many tests. Even better, as donroby said, write a unit test.
Collections.binarySearch() 怎么样？
What about Collections.binarySearch()?
JRL的所有建议都是对的，但真正的失败是你的比较颠倒了。
我自己并没有立即看到这一点，但是将代码复制到函数中（使用字符串而不是书籍），编写一些简单的 Junit 测试，然后在调试器中运行它们，这一切变得非常明显。
编写单元测试！
All of JRL's suggestions are right, but the actual fail is that your compares are reversed.
I didn't see this immediately myself, but replicating your code into a function (using strings instead of Books), writing a some simple Junit tests and then running them in the debugger made it really obvious.
Write unit tests!
我发现了问题。
事实证明，我正在对我的 bookCollection arrayList 进行二进制搜索，而不是我创建的新的 sroted 数组 -sortedLib。
我最后犯了一个愚蠢的错误，但感谢您的意见和建议！
I found the problem.
It turns out i was binary searching my bookCollection arrayList, and NOT the new sroted array i had created - sortedLib.
Silly mistake at my end, but thanks for the input and suggestions!