分而治之算法（應用二進制搜索？！）

我是新來的。作爲一名研究生，我現在已經對算法進行了頭腦風暴。我感謝任何可以延伸的關於下面問題的幫助。我已經搜索了足夠的，我找不到解決這個問題的任何解決方案。分而治之算法（應用二進制搜索？！）

我們有一個無限長的排序不同數字的數組。前n個數字是大於0但小於1的分數。所有其餘元素都是「1」，而您沒有給出n的值。您需要開發一種算法來檢查用戶給定分數F是否出現在該數組中。作爲n的函數分析算法的時間複雜度。（n = 8的示例，其中1從數組的第8個位置開始）

我的方法：我在猜測解決此問題的最佳方法是使用二分搜索。每次我們都可以將數組的大小減半，最後到達要找到的分數。讓我們假設陣列中有m個元素，包括1的元素。小數元素的數量是n。對整個數組執行二分搜索的時間複雜度爲O（log（m））。因爲我被要求用n來表示時間複雜度，所以m = n + k（假設陣列中1的數量是k）所以這個問題的時間複雜度是O（log（n + k））。

請拋開你的想法。謝謝

來源

2015-02-08 whyme

「我們有一個無限長的排序不同數字的數組。」停在那兒。現在離開計算機科學部門，去隔壁的數學系。 – 2015-02-08 15:52:54

@MikeNakis爲什麼？一些計算機科學算法需要假定非綁定值。 – ElderBug 2015-02-08 15:54:18

你不能有一個無限長度的數組。你可能會說到無盡的物品流，但不是無限的陣列。當然，您不能在流上執行二分搜索，因爲您需要知道項目的總數，以便可以計算中間值等等。 – 2015-02-08 15:57:46

你確實可以通過指數搜索來解決無限數組，即不知道m。

嘗試第一個元素並將索引加倍，直到得到1爲止。這將花費O（Lg n）個步驟。然後，您切換到二進制搜索，並在更多的O（Lg n）步驟中獲得答案。

k的值是無關緊要的。

這種方法在現實世界中是有意義的，也就是說，對於有限但未知大小的數組，假設至少有一半的數組填充了1，以便搜索終止入界。

來源

2015-02-08 16:05:48

在實踐中，你在你的指數搜索中甚至不會到1，只能到達> F的第一個元素。而且你只能在該位置和前一位置之間進行二進制搜索。當然，這不會影響最壞的情況下的時間複雜性，但它可以給你一個更好的平均情況。 – biziclop 2015-02-08 16:10:46

謝謝。有道理:) – whyme 2015-02-08 16:13:28

@biziclop：對。複雜度實際上是O（Lg i），其中i是搜索到的元素的索引。另外，我沒有說二分查找必須從第一個元素開始:)但這種優化並沒有改善平均情況，仍然是O（Lg n）或O（Lg i），它只能保留單個測試。 – 2015-02-08 16:21:11

分而治之算法（應用二進制搜索？！）

回答

相關問題