> Hi,
>
> As some of you may know I'm now taking an CS education. (At last).
> In an exercise in the course "Algorithm and complexity",
I was faced
> with this challenge:
>
> Describe an algorithm that takes two ordered sets (implemented as
> arrays) S and T (no duplicates in the two sets) of size n, and k,
to
> find the k-th smallest key in the union of S and T. The running time
> should be of order O(lg n).
>
> I've already handed in an answer, but I realize my answer is plain
> wrong. Think about this problem for a while and you will find it
> both challenging and interesting.
>
> BTW: I believe my lecturer won't have an answer to this problem
> either, and I would love see one. So, if anyone can suggest a
> working implementation, I would be really glad.
>
> -Øystein
I'm new to python hence my code is probably horrible.
Here's my idea :
Let's name S and T the two vectors.
F = {Fx = [S[i],T[j]] such that i+j+2=k} (the +2 coming from python indexing starting at 0)
Each element of F is given by a pair of indexes (i
and j) into the two vectors S and T (respectively) such that the number
of elements encompassed by the two indexes is exactly k.
Example :
S
T ======================== 2
0 3
1 7
4 8
5 12
6 14
9 15
10
For k==7, F is {[14,0], [12,1], [8,4], [7,5], [3,6],
[2,9]}. Imagine a line connecting the elements, you'll see
a kind of front moving across the two vectors (like a fluid into two
connected bottles, if you push the fluid in a bottle, the level in the
other will raise).
Notice that the last values of each array (15 and
10) are excluded since they are somehow pathological (easy to nuderstand
why).
Cx = max(Fx) : Cx is the maximum of the two values
in Fx.
Now the k-th smallest element is G = min(Cx) = min(max(Fx))
If you start from the vector with the largest element,
you can just search linearly and stop as soon as Cx changes vector.
Example :
F0 = [14,0] --> Cx = 14 (in S) F1 = [12,1] --> Cx = 12 (in S) F2 = [ 8,4] --> Cx = 8 (in S) F3 = [ 7,5] --> Cx = 7 (in S) F4 = [ 3,6] --> Cx = 6 (in T ==> STOP)
The 7th smalles element is 6.
Now the idea is to search using dicothomy ... pretty
tricky to implement however.