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

Re: Computer science algorithm problem

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

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

}

Re: Computer science algorithm problem

Quote:

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