0
$\begingroup$

Suppose we are given two ordered dictionaries S and T each with n items, and that S and T are implemented by means of array-based ordered sequences. Describe an O(log n) time algorithm for finding the kth smallest key in the union of keys from S and T. (assuming no duplicates)

I am confused on what the question is asking. I am assuming the keys are not ordered, otherwise all you would have to do is compare the first key in each dictionary, or is that what array-based ordered sequence means? Also are we creating a larger dictionary that holds both S and T inside? Would this add to the complexity if so? For the search algorithm, would we use a binary search since its complexity is O(log n)?

$\endgroup$
  • $\begingroup$ What does "ordered dictionary" mean in your course, exactly? (If the implementation is "sorted linear list", the runtime is impossible to attain.) $\endgroup$ – Raphael Nov 14 '14 at 11:26
  • 1
    $\begingroup$ See this link at stackoverflow. $\endgroup$ – hengxin Nov 14 '14 at 12:18
  • $\begingroup$ @hengxin Can you answer the question? For example, you could summarize the ideas of the algorithm, and give a link to the complete answer on stackoverflow. $\endgroup$ – Yuval Filmus Nov 14 '14 at 22:01
1
$\begingroup$

The following algorithm uses the divide-and-conquer technique. In the course of divide-and-conquer, the lengths of both sorted arrays $S$ and $T$ will change. We denote the length of $S$ (or, $T$) by $len(S)$ (or $len(T)$) at any time. Notice that I only summarize the algorithm and have intentionally omitted the tricky things about indexes (e.g., taking floor or ceiling).

Notations and Basic Idea:

At any iteration, denote the median index of $S$ by $s_m \triangleq len(S) /2$ and the median of $S$ by $S[s_m]$. Similarly, denote the median index of $T$ by $t_m \triangleq len(T) / 2$ and the median of $T$ by $T[t_m]$.

The basic idea is as follows: we compare $s_m + t_m$ with $k$ and $S[s_m]$ with $T[t_m]$ to determine which (left or right) half part of which array ($S$ or $T$) can be discarded and then we can leave the smaller sub-problem to recursion.

Algorithm:

  1. Case 1 ($s_m + t_m \geq k$):

    1.1 Case 1.1 $S[s_m] \geq T[t_m]$.

    We can discard the right bigger half of array $S$ (i.e., from $S[s_m]$ to its end). Then recursively find the $k$-th smallest element in $T$ and the left smaller half of $S$.

    1.2 Case 1.2 $T[t_m] > S[s_m]$.

    It is exactly symmetric with Case 1.1, with $T$ and $S$ exchanged.

  2. Case 2 ($s_m + t_m < k$):

    2.1 Case 2.1 $S[s_m] \geq T[t_m]$.

    We can discard the left smaller half of array $T$. Then recursively find the $(k - t_m)$-th smallest element in $S$ and the right larger half of $S$.

    2.2 Case 2.2 $T[t_m] > S[s_m]$.

    It is exactly symmetric with Case 1.1, with $T$ and $S$ exchanged.

Time Complexity:

At each iteration, we discard a half of some array. So the time complexity is $O(\lg (len(S)) + \lg (len(T)))$, which is $O(\lg n)$ for input arrays $S$ and $T$ of size $n$.

References:

  1. How to find the kth smallest element in the union of two sorted arrays?

  2. Finding kth smallest number from n sorted arrays A generalization to multiple sorted arrays.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.