# Selection problem on the union of two ordered dictionaries

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)?

• What does "ordered dictionary" mean in your course, exactly? (If the implementation is "sorted linear list", the runtime is impossible to attain.) – Raphael Nov 14 '14 at 11:26
• – hengxin Nov 14 '14 at 12:18
• @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. – Yuval Filmus Nov 14 '14 at 22:01

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.