二进制搜索问题？

可能重复：
What are the pitfalls in implementing binary search?二进制搜索问题？

我仔细阅读维基百科页面Binary Search和下面克努特无意中发现了一个报价：

“虽然二进制搜索的基本思想是：相对简单，细节可能会令人惊讶地棘手“

我reca作为我的计算机科学课程的一部分，我将实施多项二进制搜索，但不记得它非常棘手。但是，这篇文章指出，90％的被调查的专业人员在几个小时后无法工作。我想假设这不是因为这些糟糕的程序员，而是有一些天真的实现没有考虑到的边缘案例。

Knuth也提到了什么细节？如果实施二进制搜索算法，有哪些常见问题需要注意？

注意我读Bloch关于编程珍珠错误的一篇文章（int中溢出）。还有别的事吗？

来源

2011-06-16 nsfyn55

看起来像地狱重复 - 我保证。试过的问题，问题，但猜测钱的期限是'陷阱' – nsfyn55 2011-06-16 13:01:14

我刚刚发布[在重复问题的长答案]（http://stackoverflow.com/questions/504335/what-are-the-pitfalls-在-执行二进制搜索/ 6393352＃6393352）。但是没有足够长的答案来涵盖二进制搜索可能会出错的所有方法。 :-) – ShreevatsaR 2011-06-18 01:50:33

[这是一篇文章]（http://www.paultaylor.eu/algorithms/binary.html），它解释了实现二进制搜索的几种不同方法，并且有几个练习来教导行为如何改变一次你改变了界限，比较等。 – nawfal 2014-06-19 10:02:32

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

来源

2011-06-16 12:50:06 omermuhammed

哇，Knuth是你的“唐纳德”吗？ ;-) – ShreevatsaR 2011-06-16 13:48:52

呵呵，口误，最近我不得不带着我的孩子去一些知名的快餐。 – omermuhammed 2011-06-16 15:02:00

一个二进制搜索的棘手点的最佳参考的是Jon Bentley's Programming Pearls.

的whole chapter 4解决这个问题，这表明二进制搜索的很多错误的版本。

例如你想找到第一个数字大于或等于你的查询x。想想其中的问题。你怎么能证明你的程序是完全正确的？

想到这些问题，你会发现它并不那么容易。

来源

2011-06-16 12:51:24

二进制搜索问题？

回答

相关问题