2011-06-16 188 views
10

可能重複:
What are the pitfalls in implementing binary search?二進制搜索問題?

我仔細閱讀維基百科頁面Binary Search和下面克努特無意中發現了一個報價:

「雖然二進制搜索的基本思想是:相對簡單,細節可能會令人驚訝地棘手「

我reca作爲我的計算機科學課程的一部分,我將實施多項二進制搜索,但不記得它非常棘手。但是,這篇文章指出,90%的被調查的專業人員在幾個小時後無法工作。我想假設這不是因爲這些糟糕的程序員,而是有一些天真的實現沒有考慮到的邊緣案例。

Knuth也提到了什麼細節?如果實施二進制搜索算法,有哪些常見問題需要注意?

注意我讀Bloch關於編程珍珠錯誤的一篇文章(int中溢出)。還有別的事嗎?

+1

看起來像地獄重複 - 我保證。試過的問題,問題,但猜測錢的期限是'陷阱' – nsfyn55 2011-06-16 13:01:14

+1

我剛剛發佈[在重複問題的長答案](http://stackoverflow.com/questions/504335/what-are-the-pitfalls-在-執行二進制搜索/ 6393352#6393352)。但是沒有足夠長的答案來涵蓋二進制搜索可能會出錯的所有方法。 :-) – ShreevatsaR 2011-06-18 01:50:33

+0

[這是一篇文章](http://www.paultaylor.eu/algorithms/binary.html),它解釋了實現二進制搜索的幾種不同方法,並且有幾個練習來教導行爲如何改變一次你改變了界限,比較等。 – nawfal 2014-06-19 10:02:32

回答

3

我在日常工作中處於Java世界,我記得this。當我第一次讀它時,我感到很驚訝,所以這可能是唐納德談論的事情之一。

+4

哇,Knuth是你的「唐納德」嗎? ;-) – ShreevatsaR 2011-06-16 13:48:52

+1

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

2

一個二進制搜索的棘手點的最佳參考的是Jon Bentley's Programming Pearls.

whole chapter 4解決這個問題,這表明二進制搜索的很多錯誤的版本。

例如你想找到第一個數字大於或等於你的查詢x。想想其中的問題。你怎麼能證明你的程序是完全正確的?

想到這些問題,你會發現它並不那麼容易。