bug-gnubg
[Top][All Lists]

## Re: [Bug-gnubg] OT: An algorithm problem

 From: Massimiliano Maini Subject: Re: [Bug-gnubg] OT: An algorithm problem Date: Wed, 14 Feb 2007 14:16:02 +0100

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

Seems to work for me .... and it looks O(ln k)

MaX.

max-find-kth-smallest.py
Description: Binary data