在兩個排序數組中找到將它們打印在o中的公共密鑰（sqrt n）

Question

如何爲以下問題編寫僞代碼？

給出兩個排序的數組X和Y分別帶有lg n和n個鍵。我需要一種節省空間和時間的算法，可以找到X和Y共有的鍵並打印它們。它應該運行在o（sqrt n），即（小'o'）時間。

我的嘗試：你認爲二進制搜索將是一個選項嗎？

Answer 1

這是我所做的。有兩個有log（n）和n個元素的排序數組。你需要找到兩者共同的要素。

您可以迭代X和Y的每個元素的二進制搜索。如果搜索成功，則打印該元素。那將在f（x）= c *（log（n））^ 2時間，其中c是一些常數。對於每個k> 0，您可以找到一個常數a，使得所有x> a都成立，所以這個解決方案是o（sqrt（n））。

編輯：這裏是僞代碼（很簡單）：

input X 
input Y 
n = number of elements in Y 
for i = 0 to n: 
    if(binary_search(X[i] in Y) = found)print X[i] 

Answer 2

對於Shikhar的古普塔的解決方案，我有一個改進。 Shikhar的解決方案並沒有利用X進行排序的事實。因此，通過每次迭代，我們都可以減少Y的更低或更高的邊界。這也可以減少運行時間。爲了證明O（（log（n））^ 2）< O（sqrt（n）），我們只需要證明第一個的導數小於第二個。這意味着2log（n）/n < 1/sqrt（n）。那麼我們必須證明log（n）< sqrt（n）。這非常棘手。