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)