二進制搜索的用法例子

我剛剛意識到，在我4年以上的Java編程（主要是桌面應用程序）中，我從未在Arrays類中使用過二進制搜索方法來實現任何實際操作。一次也沒有。我能想到的一些原因：二進制搜索的用法例子

100％的時間你可以擺脫線性搜索，地圖或其他非二進制搜索的東西。
傳入的數據幾乎從未被排序，並且進行排序需要額外的排序步驟。

所以我想知道這是否只是我，或者做很多人從不使用二分查找？什麼是二進制搜索的一些好的，實用的例子？

2011-02-10 python dude

http://stackoverflow.com/questions/2130416/what-are-the-applications-of-binary-trees的副本？ – 2011-02-10 07:22:58

我投票結果爲重複。但是，這個問題的優點在於它解決了數據未被排序時的要點*。大多數我可以想到的用於二分查找，哈夫曼樹等的用途是當數據已經以硬拷貝格式（儘管它與MPEG文件一樣常見）呈現時。 – 2011-02-10 07:27:20

在桌面上，您可能只是處理用戶的數據，這可能不是那麼大。如果您正在查詢很多用戶共享的非常大的數據集，那麼它可能是另一回事。很多人不一定直接處理二分搜索，但使用數據庫的任何人都可能隱式使用它。例如，如果您使用AppEngine，則數據存儲區查詢幾乎可以肯定使用二進制搜索。

來源

2011-02-10 07:22:14

我想說它歸結爲：

如果我們要做一個二進制搜索，我們將有一個關鍵的搜索。如果我們有一個鍵，我們可能使用的是地圖而不是數組。

還有要記住另一個非常重要的事情：

二進制搜索是如何的思維就像一個優秀的程序員一個鮮明的例子是不是想着像正常人一樣很大的不同。這是那些認知上的飛躍之一，它讓你真正思考如何按照傳統方式完成（當人類完成時）按n次順序執行的操作，並將其降低到lg-n次。這使得它非常有用，即使它從未用於生產代碼。

來源

2011-02-10 07:22:33 corsiKa

我幾乎沒有，如果使用二進制搜索。

但我想如果：

我需要多次
名單是足夠長的有性能問題搜索相同的列表（雖然我經常會犯的微優化）

但是，我經常使用散列表/字典進行快速查找。

來源

2011-02-10 07:23:38 JohnB

對於我日常工作中的生產代碼，Set或Map到目前爲止總是足夠好。

對於我解決趣味的算法問題，二分查找是一種非常有用的技術。對於初學者來說，如果一組元素永遠不會改變（即你永遠不會插入或刪除被查詢的組中的元素），那麼Map/Set與二分查找相比沒有什麼優勢 - 並且通過簡單數組進行二分搜索可以避免很多與查詢更復雜的數據結構相關的開銷。在很多情況下，我已經看到它實際上比HashMap更快。

二元搜索也是一種比查詢一組中的成員資格更通用的技術。可以對任何單調函數執行二進制搜索以找到該函數滿足特定標準的值。你可以找到更詳細的解釋here。但正如我所說的，我的工作線沒有提出足夠的計算問題，因此無法應用。

來源

2011-02-10 07:52:30 MAK

假設您必須搜索列表中的元素。

你可以使用線性搜索，你會得到O（n）。或者，您可以通過最快的算法（O（log n）* n）和二進制搜索（O（log n））對其進行排序。你會得到O（（log n）* n + log n）。

這意味着當搜索大尺寸的列表時，二進制搜索更好。另外，它依賴於列表的數據結構。如果列表是基於鏈接的列表，則二進制搜索是不好的做法。

來源

2011-02-10 08:16:21

二進制搜索的用法例子

回答

相關問題