在n個元素的數組中使用二進制搜索找到k個不同的鍵

說，我有一個n元素的排序數組。我想使用二進制搜索在這個數組中找到兩個不同的鍵k1和k2。在n個元素的數組中使用二進制搜索找到k個不同的鍵

一個基本的解決方案是分別對它們應用二進制搜索，就像兩個2鍵調用，這將保持時間複雜度爲2（logn）。

我們可以使用任何其他方法解決這個問題的不同k鍵，k < n？

2013-12-13 Uddhav Arote

通過一次走過共享搜索路徑，您可以降低真實複雜性（儘管它仍然是大O）。也就是說，開始二元搜索，直到您所在的元素位於您正在查找的兩個項目之間。在這一點上，產生一個線程繼續二進制搜索超過你所在的軸心元素的範圍內的一個元素，併產生一個線程繼續在你所在的軸心元素之前的範圍中的另一個元素的二分搜索。返回兩個結果。 :-)

編輯：

由於奧利奇查爾斯沃思在他的評論中曾提到，你是問元素的任意量。儘管如此，這種相同的邏輯可以擴展到任意數量的搜索關鍵字。這裏有一個例子：

你的搜索關鍵字，像這樣的數組：

searchKeys = ['findme1', 'findme2', ...]

你已經發現，映射到值的搜索鍵的鍵值數據結構：

keyToValue = {'findme1': 'foundme1', 'findme2': 'foundme2', 'findme3': 'NOT_FOUND_VALUE'}

現在，按照與編輯之前相同的邏輯，你可以在每個線程產生一個「修剪」的searchKeys數組，在這個線程中鍵在主元分支。每次找到給定鍵的值時，都會更新keyToValue映射。如果沒有更多的搜索範圍，但searchKeys數組中仍有值，則可以假定找不到這些鍵，並且可以更新映射以某種方式表示（某些null的值也許？）。當所有的線程已經加入（或通過使用計數器）時，您返回映射。這裏的重大勝利是你不必重複任何兩個密鑰可能共享的初始搜索邏輯。

第二個編輯：

正如馬克在他的回答有加，排序的搜索鍵可以讓你只需要看看第一個項目的關鍵範圍。

來源

2013-12-13 04:48:29 Vinay

這可能適用於'k = 2'，但是OP在任意'k'的解決方案之後... –

^你是對的。你可以很容易地將這個概念應用到'k'項目。我會更新我的答案。 – Vinay

是的，這是一個好主意！但是，元素之間可以是右鍵之一，因此二進制搜索不能告訴你元素之間的關係！ –

您完成的每個搜索都可以用來細分輸入，以提高效率。例如，假設對應於k1的元素位於索引i1處。如果k2> k1，則可以將第二次搜索限制爲i1..n，否則將其限制爲0..i1。

最好的情況是，當您的搜索鍵也被排序時，所以每個新的搜索都可以從最後一個搜索的位置開始。

來源

2013-12-13 05:05:03

從我+1排序搜索鍵。錯過了我的答案中的細節。 :-) – Vinay

哦..對了！密鑰必須按照最佳情況排序。謝謝！ –

你可以找到學術論文，計算一般情況下不同方案的複雜性，即使用最小比較次數合併兩個可能長度不同的經過排序的序列。在http://www.math.cmu.edu/~af1p/Texfiles/HL.pdf的論文中，黃和林分析了一個最着名的方案，並參考了其他方案，以及黃和林的原始論文。

它看起來很像一個合併，逐步通過較小列表中的每個項目，沿着較大的列表跳過，這是兩個列表大小的比率。如果發現它沿着大型列表走得太遠，它可以使用二進制搜索來找到它所跨越的值之間的匹配。如果它還沒有走得夠遠，那就需要再走一步。

來源

2013-12-13 05:39:41 mcdowella

在n個元素的數組中使用二進制搜索找到k個不同的鍵

回答

相關問題