# Math Help - Computer science algorithm problem

1. ## Computer science algorithm problem

If given two arrays, Q and W which are sorted in non-decreasing order along with an integer c, how could I develop an algorithm that finds the cth smallest element in the concatenation of Q and W? The algorithm should only look at O(log c) positions of the arrays Q and W.

I've only been able to come up with ways that this would work looking at C-1 positions but not log C.

P.S. log base 2

2. ## Re: Computer science algorithm problem

I don't see why you cannot just use mergesort...

3. ## Re: Computer science algorithm problem

I found the following online.

The required kth smallest element lies within A[1]...A[k] or B[1]...B[k]. Consider the following algorithm foo():

Input:

a sorted array A
an index I_A in A
a sorted array B
an index I_B in B
an integer k

Output: The kth smallest element in the union of A[I_A]...A[I_A + k - 1] and B[I_B]...B[I_B + k - 1].
Clearly the solution to our problem is foo(A, 1, B, 1, k).

The following is an implementation of foo():

Code:
int foo(int A[], int I_A, int B[], int I_B, int k)
{
if(k == 2) return the second smallest among A[I_A], A[I_A + 1], B[I_B] and B[I_B + 1];

int M_A = A[I_A + floor(k/2)];
int M_B = B[I_B + floor(k/2)];

if (M_A < M_B)
return foo(A, I_A + floor(k/2), B, I_B, ceil(k/2));
else
return foo(A, I_A, B, I_B + floor(k/2), ceil(k/2));

}

4. ## Re: Computer science algorithm problem

Originally Posted by ShadowKnight8702
I don't see why you cannot just use mergesort...
It's probably a learning exercise. Maybe to teach independant thinking for making efficient algorithms