對Arrays.BinarySearch沒有保證？

Sun沒有提到他們的二進制搜索實現的任何複雜性。這是一個錯誤嗎？我知道它應該是O(logn)，但當他們沒有明確說明這一點時，這讓我感到緊張。他們爲他們的一些算法，比如Arrays.sort。

您是否有任何知識的實際執行？我還沒有機會自己下載源代碼！我猜這是一個簡單的二分搜索，但是Sun有時會調整算法以獲得更好的性能。

最近，http://java.sun.com/javase/6/docs/api/java/util/Arrays.html – trashgod

的java.util.Array的實現很簡單，沒有足夠的空間用於優化。

你找到JAVA_HOME/src.zip的源代碼。這個類中的排序alogrithm，這是爲了使用二進制搜索所需，是一個優化的快速排序至極提供n * log（n）性能（在許多數據集）。

2010-02-06 11:51:02 stacker

「這個類中的排序算法，這是使用二分搜索所必需的......」。要清楚的是，您不需要**使用'Array.sort（...）'。你可以確保使用任何有效的技術來排列陣列！ –

謝謝，這是不準確的 – stacker

排序算法的複雜性與binarySearch的複雜性有什麼關係？我可以使用冒泡排序來排序，然後使用'binarySearch'在O（log n）中查找元素。 – MAK

二進制搜索是通過定義O（log n）的（平均）想有沒有必要explicittly提到它。

2010-02-06 03:54:39 leeeroy

即使數組未經排序，看代碼顯然它不可能比O（日誌n）。 – SyntaxT3rr0r

@WizardOfOdds - 當然，你可能會得到錯誤的答案。 –

如果數組未經排序，doco明確表示結果未定義。 –

Arrays.sort保證返回排序後的數組，不管你是什麼數組包含。

Arrays.binarySearch(...)（小寫字母「B」 BTW）不能保證看到你的數組可能是未排序的東西。

現在編輯我的回答：看代碼顯然這是不可能比O操作表現較差（log n）的。但是，當然不能保證你會找到正確的價值。

2010-02-06 04:13:37 SyntaxT3rr0r

請問您有任何的實際執行的任何知識？

您可以在JDK安裝中或使用Google搜索自己找到實際實現的源代碼。例如，搜索「java.util.Arrays.java.html」。

但我毫不懷疑的binarySearch方法O(logN)。如果他們在過去10年左右沒有人會注意到......。

2010-02-06 04:15:39

回答