O（log n）算法找到並排預排序列表中排名爲i的元素

給定兩個排序列表，每個排序列表包含n個實數，有一個O（log n）時間算法來計算rank我假設這兩個列表中的元素是不同的，那麼這兩個列表的聯合中的哪個（我按照遞增的順序進行索引）。O（log n）算法找到並排預排序列表中排名爲i的元素

編輯： @BEN：這是我一直在做的，但我仍然沒有得到它。

我有一個例子;

列表A：1，3，5，7 列表B：2,4，6，8

查找秩（ⅰ）= 4。

第一步：I/2 = 2; 列表A現在包含爲A：1,3 列表B現在包含爲B：2,4

  compare A[i] to B[i] i.e 

       A[i] is less; 

       So the lists now become : 

        A: 3 
        B: 2,4

第二步： I/2 = 1

  List A now contains A:3 
     List B now contains B:2 

     NoW I HAVE LOST THE VALUE 4 which is actually the result ...

我知道我缺少有些事情，但即使經過近一天的思考，我不能只是想出了這一個......

來源

2010-04-24 Eternal Learner

這功課嗎？ – 2010-04-24 03:04:41

@ Ben：NOPE這不是家庭作業..我正準備參加今年夏天的一些採訪..現在你知道y :) – 2010-04-24 19:15:35

http：// stackoverflow的可能重複。com/questions/2531103/n-each-which-size-n-each-using-divide-and-conge – outis 2010-04-24 22:22:58

是：

你知道的因素在於無論是指數的第一個列表[0,i]或第二列表的[0,i]內。從每個列表中取出元素i/2並進行比較。繼續平分。

我不包括任何代碼，因爲這個問題聽起來很像作業。

編輯：二分法是二分法搜索後面的方法。它的工作原理是這樣的：

假設i = 10; （從零開始索引，我們正在尋找總體第11個元素）。

第一步，您知道答案是在list1（0 ... 10）或list2（0 ... 10）中。取a = list1（5）和b = list2（5）。

如果a> b，那麼在list1中有5個元素在a之前，而在list2中有至少6個元素在a之前。所以a是結果的上限。同樣，list2中有5個元素在b之前，而在list1中少於6個元素在b之前。所以b是結果的下限。現在我們知道結果是在list1（0..5）或者list2（5..10）中。如果一個< b，那麼結果是在列表1（5..10）或列表2（0..5）中。如果a == b，我們有我們的答案（但問題是元素是不同的，所以a = b）。

我們只是重複這個過程，在每一步中將搜索空間的大小減半。平分指的是我們選擇中間元素（平分線）超出我們所知範圍包含結果的事實。

所以這和二進制搜索之間的唯一區別是，在二進制搜索，我們比較我們正在尋找一個值，但在這裏，我們比較從另一個列表中的值。

注：這實際上是O(log i)這是優於O(log n)（至少比沒有更糟）。此外，對於小我（也許我< 100），它實際上將合併第一個元素（線性搜索，而不是平分）的操作更少，因爲這是更簡單。當你添加緩存行爲和數據局部性時，線性搜索可能會更快，因爲我可以達到幾千個。

此外，如果i>名詞然後依靠該結果必須是朝向任一列表的末尾的事實，在每個列表的初始候選的範圍是從（（上）.. N）

來源

2010-04-24 03:03:03

+1！當然，列表必須允許「O（1）」隨機訪問，但是，二進制搜索是關鍵。 – polygenelubricants 2010-04-24 03:09:30

嘿，你能指導我如何繼續做對分嗎？我對它很陌生，我在網上閱讀的大部分資料都涉及找到複數的根源。不知道如何繼續使用平分或如何正確工作。 – 2010-04-24 05:00:06

downvote的原因？ – 2010-04-24 17:12:58

當合並兩個列表，你將不得不觸摸這兩個列表中的每個元素。如果你不觸及每一個元素，一些元素將被拋在後面。因此，你的理論下限是O（n）。所以你不能這樣做。

您不必排序，因爲您有兩個已經排序的列表，您可以將該排序作爲合併的一部分進行維護。

來源

2010-04-24 02:59:13

你不必完成合並，所以它是'O（i ）'不'O（n）'。但是你可以完全避免合併。 – 2010-04-24 03:07:05

這是完全正確的。 – 2010-04-24 03:14:09

編輯：哎呀，我誤解了這個問題。我認爲有價值，你想找到排名，而不是相反。如果你想找到秩給定值，那麼這是如何做到這一點的O(log N)：

是的，你可以在O(log N)做到這一點，如果列表允許O(1)隨機存取（即它是一個數組，而不是一個鏈接列表）。

在L1二進制搜索
在L2二進制搜索
總指數

你不得不制定出數學，+ 1，-1，做什麼，如果元素沒有找到，等等，但這就是主意。

來源

2010-04-24 03:00:26 polygenelubricants

我從他試圖找到索引i處的值的問題收集到的，因此他首先得到一個索引，而不是一個值來搜索 – Phil 2010-04-24 03:03:37

你有它落後（問題是找到給定索引的值，而不是找到給定值的索引），但使用二分查找是正確的。 – 2010-04-24 03:04:02

@Ben，@Phil：你是對的，我誤解了。爲了學習的目的，我仍然保持我的答案。 – polygenelubricants 2010-04-24 03:08:15

這裏是你如何做到的。

讓第一個列表是ListX和第二列表是ListY。我們需要找到ListX[x]和ListY[y]的正確組合，其中x + y = i。由於x，y，i是自然數，我們可以立即將我們的問題域限制爲x*y。通過使用方程max(x) = len(ListX)和max(y) = len(ListY)我們現在有一個x*y元素的子集，其格式爲[x, y]，我們需要搜索。

你要做的是訂購像這樣的元素，如[i - max(y), max(y)],[i - max(y) + 1, max(y) - 1]，...，[max(x), i - max(x)]。然後，您將通過選擇中間[x, y]組合來平分此列表。由於這些列表是有序的且不同的，因此您可以測試ListX[x] < ListY[y]。如果屬實，那麼我們將上半部分的[x, y]組合對分，或者如果錯誤，則我們將下半部分平分。你會一直等到找到合適的組合。

我留下了很多細節，但這是它的一般要旨。這的確是O（log（n））！

編輯：正如本指出這其實O(log(i))。如果我們讓n = len(ListX) + len(ListY)那麼我們知道i <= n。

來源

2010-04-24 04:36:53

O（log n）算法找到並排預排序列表中排名爲i的元素

回答

相關問題