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

[Øystein Johansen]

>> 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).
>
> Hmmm ... O(lg n) or O(lg k) ?

k must be in the same order as n. Assuming that k =< n (*), you can actually do 
a initial step; reducing the two set to k elements and then finding the median 
in these two k sized elements.

(*) if (n < k < 2n) you flip the question. Find the (2n-k)-th largest element 
in the union of S and T. That should work, shouldn't it?

-Øystein