[Bug-gnubg] OT: An algorithm problem

[Øystein Johansen]

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

PS: Here's some python code that doesn't work.

import random

def os_union_find( S, T, k ):
    """ Find the k'th smallest element in the union of S and T """

    print S, T
    
    if S[-1] < T[0]:
        return S[-1]
    elif T[-1] < S[0]:
        return T[-1]

    # We need a base case when the size is of the arrays are 2
    if len(S) == 2:
        return max(S[0], T[0])
    
    mid = len(S)/2
    
    if S[mid] > T[mid]:
        return os_union_find( S[:mid], T[mid:], k/2)
    else:
        return os_union_find( S[mid:], T[:mid], k/2)

def max(a, b):
    if a > b:
        return a
    else: return b

if __name__ == "__main__":
    size = 32
    L = range(size)
    random.shuffle(L)
    S = L[:size/2]
    T = L[size/2:]
    S.sort()
    T.sort()
    # print S, "\n", T
    print os_union_find( T, S, size/2)