find the k'th smallest in two arrays algorithm(psedo code)

i have two arrays ,each of size n, which are sorted.

write an algorithm that finds the k'th smallest amongst the "sum" of the two arrays

in O(lg min (k,2n-k))

i have this idea of how to solve it.

in the added picture

i find the k smallest of array A by A[k] and k smallest of array B by B[k]

and the k smallest of the sum is between those

in my photo k2>k1

i wrote the following function but i dont know how to know if i got the k'th smallest in the recurtion.and i am not sure abiut the sub arrays ranges in the recursive calls

Mikum(A,q,r)

k1=A[k/2]

k2=B[k/2]

If (x>y)

Mikum(A,k, n)

Mikum(B,0 ,k)

http://i42.tinypic.com/1192yl5.png

Re: find the k'th smallest in two arrays algorithm(psedo code)

What is the "sum" of two arrays?

Re: find the k'th smallest in two arrays algorithm(psedo code)

sorry for the measleading term

sum is sticking to two arrays together making then into one big 2n array

for example

A 1,2,3

B 7,8,9

then we need to find the k'th smallest in 7,8,9,1,2,3 or in 1,2,3,7,8,9