在两个排序数组中查找公共键，并在 o(sqrt n) 中打印它们
Find common keys in two sorted arrays that prints them in o(sqrt n)
如何编写以下问题的伪代码？
给定两个排序数组 X 和 Y，分别具有 lg n 和 n 键。我需要一个 space 和时间高效的算法来找到 X 和 Y 的公共键并打印它们。它应该在 o(sqrt n) 内 运行，即（小 'o'）时间。
我的尝试：您认为二分查找是一种选择吗？
这是我的看法。有两个排序数组，其中包含 log(n) 和 n 个元素。您需要找到两者共有的元素。
您可以遍历 X 并在 Y 中对 X 的每个元素进行二进制搜索。如果搜索成功，则打印该元素。那将是 f(x) = c * (log(n))^2 时间，其中 c 是某个常数。
对于每个 k > 0，您可以找到一个常量 a，使得 f(x) < k * sqrt(n) 对所有 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]
对于Shikhar Gupta的解决方案，我有一个改进。 Shikhar 的解决方案没有利用 X 在每次迭代中被排序 too.So 的事实，我们可以减少 Y.This 的下限或上限也可以减少 运行 时间。
为了证明O((log(n))^2) < O(sqrt(n))，我们只需要证明一阶导数小于second.Which表示2log (n)/n < 1/sqrt(n)。然后我们必须证明 log(n) < sqrt(n)。这非常棘手。
如何编写以下问题的伪代码？
给定两个排序数组 X 和 Y，分别具有 lg n 和 n 键。我需要一个 space 和时间高效的算法来找到 X 和 Y 的公共键并打印它们。它应该在 o(sqrt n) 内 运行，即（小 'o'）时间。
我的尝试：您认为二分查找是一种选择吗？
这是我的看法。有两个排序数组，其中包含 log(n) 和 n 个元素。您需要找到两者共有的元素。
您可以遍历 X 并在 Y 中对 X 的每个元素进行二进制搜索。如果搜索成功，则打印该元素。那将是 f(x) = c * (log(n))^2 时间，其中 c 是某个常数。
对于每个 k > 0，您可以找到一个常量 a，使得 f(x) < k * sqrt(n) 对所有 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]
对于Shikhar Gupta的解决方案，我有一个改进。 Shikhar 的解决方案没有利用 X 在每次迭代中被排序 too.So 的事实，我们可以减少 Y.This 的下限或上限也可以减少 运行 时间。
为了证明O((log(n))^2) < O(sqrt(n))，我们只需要证明一阶导数小于second.Which表示2log (n)/n < 1/sqrt(n)。然后我们必须证明 log(n) < sqrt(n)。这非常棘手。