二分查找问题？

Question

10

可能重复：如何实现二分查找时的陷阱？我正在浏览维基百科关于二分查找的页面，并偶然看到 Knuth 的下面一句话:

“虽然二分查找的基本思想相对来说很简单，但是其中的细节可能会令人感到棘手。”

我记得作为计算机科学课程的一部分，我曾经实现过几次二分查找，但是并不认为它十分棘手。然而，这篇文章表明，在数小时之后，90%的调查专业人员无法使其正常工作。我想假设这不是因为这些人是糟糕的程序员，而是因为原始实现没有考虑到特殊情况。

Knuth 是指什么细节呢？如果要实现二分查找算法，有哪些需要注意的常见陷阱？

请注意，我读到 Bloch 关于 Programming Pearls 的一个错误（中点溢出）的文章。除此之外，还有什么吗？

- nsfyn55

1

看起来像重复的问题 - 我保证。尝试了问题，困难，但是猜测钱术语是“陷阱” - nsfyn55

1

我刚刚在重复的问题上发布了一篇长答案。但是没有一个答案足够长，可以涵盖二分查找可能出错的所有方式。 :-) - ShreevatsaR

这是一篇文章，讲解了几种不同的二分查找实现方式，并提供了一些练习来教授如何改变边界、比较等行为。 - nawfal

2个回答

2

二分查找中一个棘手问题的最佳参考资料之一是Jon Bentley的《编程珠玑》。

第4章涉及了这个问题，展示了许多错误的二分查找版本。

例如，你想要找到第一个大于或等于查询值x的数字。考虑其中的+1 -1问题。你如何证明你的过程是完全正确的？

思考这些问题，你会发现并不是那么容易。

- Yin Zhu

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- omermuhammed · Accepted Answer

在我的日常工作中，我处于Java世界中。我记得这个文章。当我第一次读到它时，我感到非常惊讶，所以这可能就是唐纳德所说的事情之一。